zar

Maria a primit cadou un joc. Jocul are o tablă sub formă de caroiaj dreptunghiular format din pătrăţele de latură $1$ dispuse în $L$ linii şi $C$ coloane. Pătrăţelele conţin primele $L \times C$ numere naturale nenule începând cu $1$, reprezentând coduri. Codificarea se face astfel: se începe cu valoarea $1$ din pătrăţelul din stânga-jos, se continuă cu valorile $2, 3, ..., C$ de la stânga la dreapta, continuă pe rândul următor de la dreapta la stânga şi aşa mai departe. În acest fel ultimul pătrăţel va fi codificat întotdeauna cu valoarea $L \times C$, ca în exemplul din dreapta.
Jocul constă în plasarea unui jeton în colţul din stânga jos şi trebuie să se ducă jetonul dincolo de pătrăţelul codificat cu valoarea $L \times C$ în urma mutărilor realizate. Pentru efectuarea unei mutări, el aruncă mai întâi un zar. Dacă acesta arată valoarea $Z$ şi jetonul se află în pătrăţelul cu codul $P$, jetonul va fi dus în pătrăţelul cu codul $P + Z$. Dacă $P + Z > L \times C$, jocul se termină. În caz contrar, există situaţii în care jetonul nu va rămâne neapărat în noua poziţie, întrucât în unele poziţii ale caroiajului sunt indicatoare care precizează unde trebuie dus jetonul care tocmai a ajuns în acea poziţie.

Un pătrăţel poate să conţină cel mult un indicator. Indicatoarele sunt de $9$ tipuri: pentru primele $8$ tipuri se precizează peste câte poziţii se va plasa jetonul din poziţia curentă, respectiv: pe aceeaşi linie la dreapta $(1)$, în diagonală pe direcţia dreapta-sus $(2)$, pe aceeaşi coloană în sus $(3)$, pe diagonală pe direcţia stânga-sus $(4)$, pe aceeaşi linie la stânga $(5)$, pe diagonală pe direcţia stânga-jos $(6)$, pe aceeaşi coloană în jos $(7)$, în diagonală pe direcţia dreapta-jos $(8)$. Indicatorul de tipul $9$ precizează codul unui pătrăţel în care va fi plasat jetonul.
La aplicarea unui indicator se respectă regulile:
a) dacă jetonul iese în afara tablei, acest indicator va fi neglijat, iar jetonul va rămâne pe loc (jocul nu se poate termina astfel).
b) dacă se ajunge într-un pătrăţel care conţine un alt indicator, acesta nu va mai fi luat în considerare.

Cerinţă

Cunoscând, în ordine, cele $K$ valori obţinute în urma aruncărilor cu zarul, să se determine dacă jocul se poate încheia. În caz afirmativ se va afişa numărul de aruncări cu zarul după care jocul se încheie. În caz contrar, se va afişa poziţia jetonului după cele $K$ mutări.

Date de intrare

Fişierul de intrare zar.in conţine pe prima linie două numere $L$ şi $C$ reprezentând numărul de linii, respectiv numărul de coloane ale tablei de joc. Pe linia a $2$-a se găseşte un număr natural $I$ reprezentând numărul de pătrăţele în care se găsesc indicatoare. Pe următoarele $I$ linii se găsesc câte $3$ numere naturale separate prin câte un spaţiu reprezentând descrierea câte unui indicator. Primul număr este codul pătrăţelului în care este pus indicatorul, al doilea număr este tipul de indicator. Dacă tipul de indicator este $9$, al treilea număr semnifică codul pătrăţelului unde va fi trimis jetonul. Dacă al doilea număr este din mulţimea $\{1, 2, 3, 4, 5, 6, 7, 8\}$, al treilea număr reprezintă numărul de poziţii de pe tablă peste care se va muta jetonul în direcţia precizată. Pe linia următoare se află un număr natural $K$ reprezentând numărul de aruncări cu zarul. Pe următoarea linie sunt $K$ numere naturale separate prin câte un spaţiu, reprezentând, în ordine, valorile obţinute după fiecare aruncare.

Date de ieşire

Fişierul de ieşire zar.out va conţine pe prima linie două numere naturale separate printr-un spaţiu. Dacă jocul se termină, prima valoare va fi $1$, iar a doua va reprezenta numărul de mutări după care s-a terminat. Dacă jocul nu se termină, prima valoare va fi $2$, iar a doua codul pătrăţelului unde a rămas jetonul.

Restricţii şi precizări

• $1 \leq L, C \leq 50$
• $0 \leq I \leq L \times C$
• $1 \leq K \leq 1 \ 000$
• Valorile obţinute în urma aruncărilor cu zarul sunt numere din mulţimea $\{1, 2, 3, 4, 5, 6\}$;
• Numărul de poziţii cu care se poate deplasa jetonul pentru un indicator de tip de la $1$ la $8$ este număr întreg nenul $\leq 50$

Exemplu

zar.in

3 4
4
3 2 1
8 1 1
7 1 2
9 9 11
4
2 1 2 2

zar.out

2 11

Explicaţie

Iniţial jetonul este în pătrăţelul $1$. După prima mutare el ajunge în pătrăţelul $5$ (zarul arată $2$ şi jetonul ar ajunge în pătrăţelul $3$ dar indicatorul de acolo în trimite în pătrăţelul 5). După mutarea a doua jetonul ajunge în pătrăţelul $6$ (acolo îl trimite zarul şi nu este întâlnit un indicator). După mutarea a treia, jetonul ajunge în pătrăţelul $7$ (zarul îl trimite în $8$, iar indicatorul de acolo în $7$ – acum nu se ţine cont de indicatorul din $7$). După mutarea $4$ jetonul ajunge la pătrăţelul $11$ (după aruncarea cu zarul trebuia dus în $9$ iar indicatorul de acolo îl trimite în $11$).