eliberare

Se organizează cel mai grandios eveniment în aer liber pentru șoferi: Drive-in cinema cu o parcare imensă matriceală pentru mașini, cu patru ecrane imense la nord, sud, est și vest. Același film este proiectat în toate cele patru direcții. Altfel spus, ai la dispoziție $360^\circ$ de film, deci, oricum ai parca, vei putea viziona filmul fără probleme consumând Tortilla chips cu gust de brânză și Coca-Cola.

Mașinile sosesc în parcare una după alta, având loc și timp suficient să efectueze manevre sigure de parcare. Însă, la finalul evenimentului, toate mașinile vor dori să plece cât mai repede. De aceea, este nevoie de o strategie prin care mașinile să părăsească parcarea în linie dreaptă (fără viraje), păstrând direcția în care erau așezate în timpul filmului, fără să se ciocnească cu alte mașini. Parcarea fiind într-o zonă deschisă, se poate ieși pe oriunde. Altfel spus: tot perimetrul matricei este ieșire. Organizatorii vă roagă să dați o mână de ajutor cu o strategie prin care să eliberați mașinile din parcare una câte una, precizând de fiecare dată coordonatele (linia și coloana) următoarei mașini care pleacă.

Parcarea arată ca o matrice cu $N$ linii și $M$ coloane, pe fiecare loc de parcare fiind câte o mașină parcată către una din direcțiile: Nord (caracterul ^), Sud (caracterul v), Est (caracterul >), sau Vest (caracterul <). De exemplu, imaginea cu mașinuțele de mai sus reprezintă primul exemplu: $N = 3$ linii și $M = 4$ coloane, iar matricea corespunzătoare se regăsește în imaginea din dreapta.

Aici, o strategie de eliberare este următoarea:

1. Se eliberează mașina de pe $(1, 4)$ — spre Nord, nu are niciun obstacol;
2. Se eliberează mașina de pe $(1, 2)$ — spre Nord, nu are niciun obstacol;
3. Se eliberează mașina de pe $(1, 1)$ — spre Vest, nu are niciun obstacol;
4. Se eliberează mașina de pe $(1, 3)$ — spre Est, mașina din calea ei a plecat deja;
5. Se eliberează mașina de pe $(2, 1)$ — spre Nord, mașina din calea ei a plecat deja;
6. Se eliberează mașina de pe $(2, 3)$ — spre Nord, mașina din calea ei a plecat deja;
7. Se eliberează mașina de pe $(2, 4)$ — spre Est, nu are niciun obstacol;
8. Se eliberează mașina de pe $(2, 2)$ — spre Est, mașinile din calea ei au plecat deja;
9. Se eliberează mașina de pe $(3, 4)$ — spre Sud, nu are niciun obstacol;
10. Se eliberează mașina de pe $(3, 3)$ — spre Est, mașina din calea ei a plecat deja;
11. Se eliberează mașina de pe $(3, 2)$ — spre Sud, nu are niciun obstacol;
12. Se eliberează mașina de pe $(3, 1)$ — spre Est, fiind ultima, are cale liberă.

Cerință

Cunoscând dimensiunile parcării $N$, $M$ și direcția fiecărei mașini, se cere un plan de eliberare a tuturor mașinilor.

Date de intrare

Prima linie va conține numărul de linii $N$ și numărul de coloane $M$, separate printr-un spațiu. Pe următoarele $N$ linii, se vor regăsi câte $M$ caractere neseparate prin spații din mulțimea {^, v, >, <}, semnificând direcțiile în care sunt parcate mașinile.

Date de ieșire

Se vor tipări în ordinea eliberării pe $N \times M$ linii câte două numere naturale lin și col separate printr-un spațiu, reprezentând coordonatele câte unei mașini eliberate (lin, col).

Restricții și precizări

• $1 \leq N, M \leq 1 \ 100$
• Pentru toate testele de evaluare există soluție.
• Soluția nu este neapărat unică — orice soluție corectă se acceptă.
• Mașinile nu pot fi eliberate parțial — la momentul eliberării sale, o mașină trebuie să aibă cale liberă până la marginea parcării.
• Note tipografice:
  • Caracterul ^ este cel folosit în C / C++ pentru operația xor (sau exclusiv pe biți).
  • Caracterul v este litera latină v mic, nu litera V mare.
  • Caracterele > și < sunt cele folosite în matematică cu sensul de "mai mare" și "mai mic".

Exemplul 1

eliberare.in

3 4
<^>^
^>^>
>v>v

eliberare.out

1 1
1 2
1 4
1 3
2 1
2 3
2 4
2 2
3 2
3 4
3 3
3 1

Explicație

O altă soluție corectă pentru exemplul din enunț.

Exemplul 2

eliberare.in

2 3
>^v
<^<

eliberare.out

1 2
2 2
2 1
2 3
1 3
1 1

Explicație

1. Se eliberează mașina de pe $(1, 2)$ — spre Nord, nu are niciun obstacol;
2. Se eliberează mașina de pe $(2, 2)$ — spre Nord, mașina din calea sa a fost deja eliberată;
3. Se eliberează mașina de pe $(2, 1)$ — spre Vest, nu are niciun obstacol;
4. Se eliberează mașina de pe $(2, 3)$ — spre Vest, mașinile din calea ei au fost deja eliberate;
5. Se eliberează mașina de pe $(1, 3)$ — spre Sud, mașina din calea ei a fost deja eliberată;
6. Se eliberează mașina de pe $(1, 1)$ — spre Est, fiind ultima, are cale liberă.