Un astronaut al ASR (Agentia Spatiala Romana) a fost "uitat" pe al $N$-lea nivel al unei statii spatiale romanesti. El vrea sa coboare pana la nivelul $1$, unde sunt localizate dispozitivele de comunicatie, pentru a putea contacta o nava spatiala care sa-l recupereze. Din nefericire, astronautul nu stie cat de mult timp i-ar lua navei spatiale pentru a ajunge la statie; de aceea, astronautul vrea sa adune cat mai multa mancare spatiala inainte de a chema nava spatiala.

Fiecare nivel al statie spatiale contine $16$ camere, aranjate sub forma unei matrice cu $4$ linii si $4$ coloane (liniile sunt numerotate de la $1$ la $4$; la fel si coloanele). Fiecare camera contine o cantitate de mancare spatiala. Astronautul se poate deplasa liber in interiorul statiei spatiale, dar nu poate vizita aceeas camera de $2$ ori. Mai mult, o data ce a coborat la un nivel inferior, el nu mai poate urca pe un nivel de deasupra. In fiecare zi, din camera in care se afla, astronautul se poate muta ori in camera localizata la nord, la sud, la est sau la vest fata de camera curenta (pe acelasi nivel) sau in jos, pe nivelul de dedesubt, in camera de pe aceeasi linie si coloana ca si camera curenta. Deplasarea in jos este permisa numai daca exista o usa catre nivelul de dedesubt in camera curenta. Pentru fiecare nivel, astronautul are la dispozitie o harta care ii arata ce camere au usi catre nivelul de dedesubt. Astronautul nu sta $2$ zile la rand in aceeasi camera si in fiecare zi se muta doar o singura data.

Fiecare nivel al statie spatiale contine $16$ camere, aranjate sub forma unei matrice cu $4$ linii si $4$ coloane (liniile sunt numerotate de la $1$ la $4$; la fel si coloanele). Fiecare camera contine o cantitate de mancare spatiala. Astronautul se poate deplasa liber in interiorul statiei spatiale, dar nu poate vizita aceeasi camera de $2$ ori. Mai mult, o data ce a coborat la un nivel inferior, el nu mai poate urca pe un nivel de deasupra. In fiecare zi, din camera in care se afla, astronautul se poate muta ori in camera localizata la nord, la sud, la est sau la vest fata de camera curenta (pe acelasi nivel) sau in jos, pe nivelul de dedesubt, in camera de pe aceeasi linie si coloana ca si camera curenta. Deplasarea in jos este permisa numai daca exista o usa catre nivelul de dedesubt in camera curenta. Pentru fiecare nivel, astronautul are la dispozitie o harta care ii arata ce camere au usi catre nivelul de dedesubt. Astronautul nu sta $2$ zile la rand in aceeasi camera si in fiecare zi se muta doar o singura data.

De fiecare data cand intra intr-o camera, astronautul ia cantitatea de mancare spatiala aflata in camera respectiva. Ratia de mancare a unui astronaut este definita ca raportul dintre cantitatea totala de mancare spatiala adunata in timpul plimbarii sale prin statie si numarul de zile petrecute in interiorul statiei spatiale inainte de a chema nava spatiala. Se considera ca astronautul petrece prima zi in camera unde isi incepe calatoria, pe nivelul $N$, si ca ia cantitatea de mancare din camera respectiva.

h2. Date de intrare

Prima linie a fisierului de intrare $lost.in$ contine un singur numar intreg $N$, reprezentand numarul de nivele ale statiei spatiale. Urmeaza apoi descrierile celor $N$ nivele, in ordine, de la nivelul $N$ la nivelul $1$. Pentru fiecare nivel, vor exista $8$ linii in fisierul de intrare. Primele $4$ linii contine cate $4$ numere intregi, reprezentand cantitatea de mancarea spatiala disponibila in fiecare camera de pe nivelul respectiv (al $j$-lea numar de pe a $i$-a linie dintre cele $4$ va reprezenta cantitatea de mancare din camera de pe linia $i$ si coloana $j$). Urmatoarele $4$ linii vor contine cate $4$ numere intregi, avand valorile $0$ sau $1$. $1$ inseamna ca exista o usa din camera respectiva catre nivelul de dedesubt, iar $0$ inseamna ca nu exista usa. Nivelul $1$ va avea numai valori $0$ pe aceste $4$ linii. Ultima linie a fisierului contine $2$ numere intregi, $l$ si $c$, reprezentand linia si coloana camerei de pe nivelul $N$ in care se afla initial astronautul.

Prima linie a fisierului de intrare $lost.in$ contine un singur numar intreg $N$, reprezentand numarul de nivele ale statiei spatiale. Urmeaza apoi descrierile celor $N$ nivele, in ordine, de la nivelul $N$ la nivelul $1$. Pentru fiecare nivel, vor exista $8$ linii in fisierul de intrare. Primele $4$ linii contin cate $4$ numere intregi, separate prin cate un spatiu, reprezentand cantitatea de mancarea spatiala disponibila in fiecare camera de pe nivelul respectiv (al $j$-lea numar de pe a $i$-a linie dintre cele $4$ va reprezenta cantitatea de mancare din camera de pe linia $i$ si coloana $j$). Urmatoarele $4$ linii vor contine cate $4$ numere intregi, separate prin cate un spatiu, avand valorile $0$ sau $1$. $1$ inseamna ca exista o usa din camera respectiva catre nivelul de dedesubt, iar $0$ inseamna ca nu exista usa. Nivelul $1$ va avea numai valori $0$ pe aceste $4$ linii. Ultima linie a fisierului contine $2$ numere intregi, $l$ si $c$, reprezentand linia si coloana camerei de pe nivelul $N$ in care se afla initial astronautul.

h2. Date de iesire

Pe prima linie a fisierului de iesire $lost.out$ veti afisa ratia maxima de mancare pe care o poate obtine astronautul, cu $4$ cifre zecimale. Pe a doua linie veti afisa lungimea drumului sau (afisati $0$ daca astronautul nu iese din camera in care se afla initial). Daca lungimea drumului sau este $L$ ({$L > 0$}), atunci pe a trei alinie veti afisa $L$ caractere din multimea ${'N','E','S','W','D'}, fiecare caracter corespunzand unei directii de miscare (nord, est, sud, vest si jos). Daca exista mai multe drumuri cu aceeasi ratie maxima de mancare, puteti afisa oricare din ele.

Pe prima linie a fisierului de iesire $lost.out$ veti afisa ratia maxima de mancare pe care o poate obtine astronautul, cu $4$ cifre zecimale. Pe a doua linie veti afisa lungimea drumului sau (afisati $0$ daca astronautul nu iese din camera in care se afla initial). Daca lungimea drumului sau este $L$ ({$L > 0$}), atunci pe a treia linie veti afisa $L$ caractere din multimea ${'N','E','S','W','D'}$, fiecare caracter corespunzand unei directii de miscare (nord, est, sud, vest si jos). Daca exista mai multe drumuri cu aceeasi ratie maxima de mancare, puteti afisa oricare din ele.

h2. Restrictii