Zadanie
Iniciatívna výpomoc
Počet bodov: 65
Ako už je v tejto krajine zvykom, v období Veľkej Noci stúpa dopyt po ananásoch za účelom maľovania kraslíc. Ak ste ešte kraslice nemaľovali, postup je celkom jednoduchý a odporúčame vám si ho niekedy vyskúšať. Jednoducho zoberiete zrelý ananás, odstrihnete mu vlasy, na vrchu a spodku škrupiny spravíte dierku a do jednej z nich s citom fúknete. Druhou dierkou vám potom vytečie ananásový džús a vy môžete zvyšnú dutú škrupinu namaľovať ornamentami podľa svojej chuti. Každopádne, vašou úlohou momentálne nebude tvoriť kraslice ale zbierať ananásy. Ujo Kubík potrebuje vašu pomoc, keďže sám všetky plody svojej ananásovej farmy nestíha a nezvláda pozbierať. Kubík vlastní rozľahlé úrodné pole na ktorom rastú hŕby ananásov, ktoré avšak nerastú veľmi systematicky. Vašou úlohou bude teda sedieť na streche Kubíkovho traktora a navigovať ho ku každému ananásu ktorý uvidíte.
Úloha
Traktor je nemotorný a tak zvláda pohyb iba v ôsmich smeroch svetových strán. Ujovi budete teda zo strechy kričať vždy ktorým z ôsmych smerov má ísť a ako dlho. Pre jednoduchosť budete pre šikmé smery hovoriť koľko uhlopriečok jednotkového štvorca treba prejsť. Keďže traktory sú hlučné a palivo drahé, prioritizujte navigáciu, ktorá použije čo najmenej príkazov, a v prípade remízy takú, ktorá prejde čo najmenšiu vzdialenosť.
Smery budeme označovať N pre sever (rastúca y-ová súradnica), S pre juh, E pre východ (rastúca x-ová súradnica) a W pre západ. Zvyšné štyri šikmé smery označujeme NE, NW, SE, SW.
Aby naozaj nenastal zmätok v tom ktorú navigáciu máte zakričať, v prípade remízy počtu príkazov aj prejdenej vzdialenosti uprednostnite trasu, ktorej postupnosť smerov je lexikograficky najmenšia. Lexikografické usporiadanie svetových strán je E, N, NE, NW, S, SE, SW, W. Teda postupnosť smerov (N, S, W) < (N, SE, E) lebo N = N a S < SE.
Každý zber ananásu vieme opísať jednoducho súradnicami vašej aktuálnej pozície a pozície ananásu. Vašou úlohou je zakričať najlepšiu postupnosť príkazov podľa hodnotenia uvedeného vyššie.
Vstup a výstup
Na prvom riadku vstupu máte číslo \(0 \leq Q \leq 10000\), počet zberov. Nasleduje \(Q\) riadkov, na každom z nich štyri celé čísla \(0 \leq |x_1|, |y_1|, |x_2|, |y_2| \leq 10^6\) označujúce súradnice vašej aktuálnej pozície a pozíciu ananásu. Platí \((x_1, y_1) \neq (x_2, y_2)\).
Na výstup vypíšte \(Q\) navigácii pre dané zbery. Na prvom riadku navigácie vypíšte počet príkazov a následne daný počet riadkov s príkazmi, na každom riadku medzerou oddelený smer a počet krokov v danom smere.
Príklady
Input:
2
0 0 1 1
0 0 1 2Output:
1
NE 1
2
N 1
NE 1