2. Raz sa stratiť musím

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Stankovi na email [email protected]

Cez zimu sa veľmi oteplilo, a tak sa Hanka rozhodla, že sa pôjde prejsť po Petržalke. Hanka má však obrovský talent, takzvaný “orientačný nezmysel”. To znamená, že sa dokáže stratiť aj na miestach, kde by si si povedal/a, že to je nemožné. Keďže o tejto svojej schopnosti vedela, tak si zobrala kompas a na každej križovatke si zapísala ktorým smerom išla daľej. Keďže ale budovy aj križovatky v Petržalke sú všetky na prvý pohľad rovnaké, tak sa hneď stratila a odbočila preč od svojej plánovanej cesty. Preto jej teda musíte pomôcť zistiť kde je, aby potom nejako trafila naspäť domov.

Úloha

Tvojou úlohou je zistiť Hankinu výslednú pozíciu z toho, ktorými smermi odbočovala. Mapu Petržalky si vieme predstaviť ako dokonalú štvorčekovú sieť s \(r\) riadkami a \(s\) stĺpcami, kde križovatky sú mrežové body. Hanka začína na križovatke so súradnicami \(p_y\), \(p_x\). Ďalej platí, že okolo mesta nič nie je, takže vždy ak Hanka zistila, že odbočila mimo mesta¹, tak sa otočila a vrátila na predchádzajúcu križovatku v meste, kde bola predtým.

Formát vstupu

Na prvom riadku vstupu dostanete 3 medzerou oddelené čísla \(r\), \(s\), \(n\) – označujúce počet riadkov mapy (výšku mapy), stĺpcov mapy (šírku mapy) a dĺžku Hankinej cesty. Platí, že \(1 \leq r, s \leq 10^9\), \(1 \leq n \leq 10^6\).
Na druhom riadku je dvojica čísel \(p_y\), \(p_x\) – Hankina počiatočná pozícia. Prvé číslo označuje riadok a druhé stĺpec na mape, kde sa Hanka na začiatku nachádzala.
Platí, že \(0 \leq x \leq s\), \(0 \leq y \leq r\). Na treťom riadku je opis samotnej cesty – reťazec znakov SJVZ. Znaky v ceste nie sú oddelené medzerou.

Riadky siete číslujeme od nuly, od vrchu mapy. Stĺpce číslujeme tiež od nuly z ľavej strany mapy

Je 5 sád vstupov, za každú správne vyriešenú máš 20 bodov. Pre jednotlivé sady platia nasledovné obmedzenia:

Formát výstupu

Na výstup vypíš Hankinu výslednú pozíciu ako dve medzerou oddelené čísla. Najprv vypíš y-ovú súradnicu a potom x-ovú.

Príklad

Input:

4 5 10
1 2
JVJZZSSVVV

Output:

1 4

Hanka sa v tomto prípade pohybovala takto:

Input:

4 5 7
1 0
VSSVJJV

Output:

2 3

Hanka sa teraz sa hýbala takto. Všimnite si, že po druhom kroku išla hore, nakoľko ale odišla von z mesta, musela sa vrátiť naspäť.