Liniile şi coloanele matricii sunt numerotate de la $1$ la $N$. Dacă la secunda $T$ o furnică se află spre exemplu 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 (<)$.

Iar acum, cerinţa. Alinuţa vrea să ştie după câte secunde se vor întâlni pentru prima oară două furnici în această matrice. Ea consideră că două furnici se întâlnesc dacă păşesc în aceeaşi secundă pe acelaşi pătrăţel din matrice. Oare are vreun sens să o ajutaţi pe Alinuţa să găsească răspunsul la această cerinţă?

Iar acum, cerinţa. Alinuţa vrea să ştie după câte secunde se vor întâlni pentru prima oară două furnici în această matrice. Ea consideră că două furnici se întâlnesc dacă păşesc în aceeaşi secundă pe acelaşi pătrăţel din matrice. Daca nu exista doua furnici care sa se intalneasca vreodata afisati doar -1. Oare are vreun sens să o ajutaţi pe Alinuţa să găsească răspunsul la această cerinţă?

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $coliziuni.out$ se vor găsi $T$ linii cu câte un număr natural fiecare, reprezentând numărul de secunde după care se vor întâlni pentru prima oară două furnici între ele, pentru fiecare test în parte.

În fişierul de ieşire $coliziuni.out$ se vor găsi $T$ linii cu câte un număr intreg fiecare, reprezentând numărul de secunde după care se vor întâlni pentru prima oară două furnici între ele, sau $-1$ daca nu se intampla vreodata asta, pentru fiecare test în parte.

h2. Restricţii

-1
|

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="coliziuni") ==