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.

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.

h2. Date de ieşire

Î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.

Î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.

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