Červená Čiapočka si ďalej kráča lesom, kráča a tu zrazu naďabí na krík s malinami. “Ale však babka by sa nehnevala, keby som zopár malín pozbierala.” A tak Čiapočka zbiera maliny, zbiera, a tu zrazu naďabí na černice. “Ale však babka by sa nehnevala, keby som aj zopár černíc pozbierala.” A tak zbiera černice, zbiera, a tu zrazu naďabí na šípky. “Ale však babka by sa ani vtedy nehnevala, keby som aj zopár šípok pozbierala.” A teda zbiera a zbiera, a tu zrazu - stratila sa v húšti šípkových kerov. Pomôž Červenej Čiapočke nájsť cestu späť k chodníku k babkinmu domu.
Šípkové húštie vyzerá ako tabuľka $r \times s$ vyplnená znakmi >, <, ^ a v. Každé políčko je teda šípka hore, doľava, doprava alebo dole. Červená Čiapočka začína na počiatočnej pozícii $X, Y$ a v jednom kroku sa posunie v smere aktuálnej šípky o jedno políčko. Ak šípka ukazuje von z tabuľky, tak sa dostane von z húštia a už dokonca zostane vonku. Je daný počet krokov $k$. Zistite, kde sa bude Červená Čiapočka nachádzať danom počte krokov.
Políčko v tabuľke vieme označiť jeho súradnicami, teda číslom stĺpcu a riadku, v ktorom sa nachádza. Čísluje sa od nuly, teda napríklad prvý stĺpec a druhý riadok je $0, 1$.
Na vstupe sú na prvom riadku celé čísla $s$, $r$, počet stĺpcov a riadkov tabulky, počet krokov $k$ a štartovné súradnice $x, y$. Čísla sú oddelené medzerou.
Nasleduje $r$ riadkov tabuľky zo znakov >, <, ^ a v, každý po $s$ znakoch.
| Sada | 1 | 2 | 3 |
|---|---|---|---|
| $r, s \leq$ | $70$ | $1000$ | $1000$ |
| $k \leq$ | $5000$ | $10^6$ | $2 \times 10^{12}$ |
Na jeden riadok vypíš súradnice, na ktorých skončila Červená Čiapočka po $k$ krokoch. Ak je v tabuľke, vypíš číslo stĺpcu a riadku, oddelené medzerou. Ak sa dostala von, vypíš VONKU.
2 2 5 0 0
>v
^<
1 0
Začína vľavo hore a chodí do kruhu v smere hodinových ručičiek, takže po piatich krokoch bude vľavo hore.
2 2 5 0 0
>v
^>
VONKU
Začína vľavo hore, pôjde doprava, dole, doprava, a tým sa dostane von z húštia. Ďalšie kroky už nebude robiť.