Alinuţa are de compus pentru şcoală o poezie despre furnici. Da, chiar aşa este, nu vă mint... De aceea, fetei i-a venit ideea că ar fi bine să studieze aceste *insecte sociale* înainte să îşi ducă la bun sfârşit această temă de mare importanţă.

Aşa că Alinuţa şi-a cumpărat $M$ furnici, şi le-a aşezat pe toate într-o matrice de dimensiuni $N x N$.

Aşa că Alinuţa şi-a cumpărat $M$ furnici, şi le-a aşezat pe toate într-o matrice de dimensiuni $N x N$. Fiecare furnică ocupă astfel exact o pătrăţică din matrice. Alinuţa le-a dat furnicilor şi o direcţie iniţială (fiecare furnică este îndreptată într-una din cele $4$ direcţii (N, S, E, V), codificate (^, v, >, <). Sper că totul este clar până aici. Chiar nu vă mint.
 
Iar acum, Alinuţa a început să observe aceste furnici şi a observat că în fiecare secundă, toate furnicile fac un pas în direcţia către care sunt îndreptate. Fiind însă nişte insecte algoritmice, ele ştiu că nu trebuie să părăsească matricea. Aşa că, în secunda în care sunt pe cale de a ieşi din aceasta, ele preferă în schimb să se întoarcă cu 180 grade. Nu cred că s-a înţeles foarte bine... Hai să luăm un exemplu.
 
Liniile şi coloanele matricii sunt numerotate de la $1$ la $N$. Dacă la secunda $T$ o furnică se află pe căsuţa $(1, N)$ şi se îndreaptă către $EST (>)$, atunci la secunda $T + 1$ ea se va afla tot pe căsuţa $(1, N)$ dar va fi îndreptată către $VEST (<)$.

h2. Date de intrare