Problem F
Hoppers

Joshua har byggt en fabrik i minecraft som består av ett rutnät där varje ruta innehåller en s.k. hopper. En hopper kan förvara en sak i sig, och pekar dessutom på en annan hopper som ligger antingen direkt över, under, till vänster eller höger om hoppern. En gång per sekund puttar varje hopper saken de har i sig till hoppern de pekar på om de har något i sig. Ibland kan detta leda till att en hopper har mer än en sak i sig samtidigt. Detta funkar självklart inte, eftersom alla sakerna som puttades in i hoppern den sekunden då förstörs.

Joshua vill ha en stabil fabrik utan en massa krockar. Han ger därför ett förslag till dig om hur sakerna ska placeras och hur fabriken ska se ut, och vill nu veta för varje sak om den kommer krocka eller åka runt i fabriken för all oändlighet. För alla saker som krockar vill han dessutom veta var krocken skedde så han sedan kan uppdatera sin design. Skriv ett program för att hjälpa honom!

 

Figure 1: Fabriken i exempelfall 1 innan den startat och efter en sekund. Notera att tre saker krockar vid rutan i mitten.

Indata

Den första raden innehåller tre heltal $R, C$ ($2 \le R \cdot C \le 10^6$), $N$ ($1 \le N \le 10^5$), antalet rader respektive kolumner i fabriken och antalet saker som ska stoppas in i förslaget.

Därefter följer $R$ rader, där varje rad består av en sträng med $C$ tecken och tillsammans beskriver hur fabriken ser ut. Varje tecken i rutnätet berättar vilken riktning hoppern på den rutan pekar åt. Tecknen kommer antingen vara ’v’ (ner), ’<’ (vänster), ’^’ (upp) eller ’>’ (höger). Det är garanterat att varje hopper pekar på en annan hopper.

Därefter följer $N$ rader, med två heltal $P_ r$ ($0 \le P_ r \le R-1$) och $P_ c$ ($0 \le P_ c \le C-1$), raden och kolumnen som den $i$:te saken börjar på. Ingen hopper innehåller två eller fler saker i början.

Utdata

För varje sak i samma ordning som i indatan, skriv ut en rad med "cycle" om saken aldrig krockar med något, eller "$r$ $c$" om den krockar med något i hoppern på rad $r$ och kolumn $c$ ($0$-indexerat).

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 3 5
vvv
>v<
>>^
0 1
1 0
1 2
2 0
2 2

1 1
1 1
1 1
cycle
cycle

1 2 2
><
0 0
0 1

cycle
cycle

3 3 3
vvv
v<<
>^^
0 0
0 2
2 2

cycle
1 2
1 2