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 (<)$.

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ţă?
 

h2. Date de intrare
Fişierul de intrare $coliziuni.in$ conţine pe prima linie numerele $N$ şi $M$, având semnificaţia din enunţ. Pe fiecare linie din următoarele $M$ se vor găsi direcţia furnicii (reprezentată printr-un caracter $^, v, >, <$), şi două numere naturale $X$ şi $Y$, reprezentând poziţia iniţială a furnicii.