h2. Date de intrare

Fişierul de intrare $coliziuni.in$ conţine pe prima linie numărul de teste, $T$. Fiecare test are următoarea structură: pe prima linie se află 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.

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.

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 va găsi un singur număr natural, reprezentând numărul de secunde după care se vor întâlni pentru prima oară două furnici între ele.

h2. Restricţii

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 50.000$
* $1 ≤ T ≤ 1000$
* Suma tuturor valorilor lui $M$ în cadrul aceluiaşi fişier de intrare nu va depăşi valoarea $250.000$.
* Pentru 40% din punctaj: $T = 10$, $N ≤ 2000, M ≤ 500$

* $... ≤ ... ≤ ...$

h2. Exemplu