piticot

Pe vremea mea toţi copiii erau pasionaţi de Piticot. Tabla de joc este frumos colorată şi are pe ea marcat un traseu cu anumite puncte cheie marcate prin $L$ cerculeţe, numerotate de la $1$ la $L$ în ordinea de pe traseu. Fiecare jucător are un pion, iar la începutul jocului toţi pionii sunt plasaţi pe cerculeţul de start (cerculeţul cu numărul $1$). Scopul jocului este ca pionul tău să ajungă primul în cerculeţul final (cel care are numărul $L$).

Jucătorii mută alternativ. Când îi vine rândul, jucătorul dă cu zarurile obţinând astfel un număr aleator, apoi mută pionul său înainte cu un număr de cerculeţe egal cu numărul aleator obţinut. Dacă numărul aleator este mai mare decât numărul de cerculeţe până la cerculeţul final, pionul se opreşte în cerculeţul final.

Anumite cerculeţe de pe traseu au asociate anumite acţiuni (de exemplu, Fă doi paşi înapoi!, Fă un pas înainte!, Mai dă o dată cu zarul!). Când ajunge pe un cerculeţ cu o acţiune asociată jucătorul trebuie să execute acţiunea respectivă. Cerculeţul de start şi cel final nu au nici o acţiune asociată.

Pentru a afla numerele aleatoare obţinute de jucători atunci când dau cu zarul, vom utiliza un generator de numere aleatoare care are ca parametri numerele naturale $a, b, c$ şi $x_0$. Generatorul produce o secvenţă de numere naturale $x_1, x_2, x_3, \dots$ după următoarea regulă: $x_{n+1}=(a \cdot x_n+b) \% c$ (unde $\%$ semnifică restul împărţirii întregi), pentru $n=0, 1, 2, \dots$ În timpul jocului se utilizează în ordine numerele aleatoare $x_1, x_2, x_3, \dots$ ($x_0$ nu este utilizat în joc).

Cerinţă

Scrieţi un program care, cunoscând tabla de joc, parametrii generatorului de numere aleatoare şi numărul de jucători, să determine cine va fi câştigătorul jocului (cine ajunge primul în cerculeţul final).

Date de intrare

Fişierul de intrare piticot.in conţine pe prima linie $4$ numere naturale separate prin spaţiu $a \ b \ c \ x_0$ reprezentând parametrii generatorului de numere aleatoare. Pe cea de a doua linie se află două numere naturale separate prin spaţiu $K \ L$, $K$ reprezentând numărul de jucători, iar $L$ numărul de cerculeţe de pe traseul de pe tabla de joc.

Considerăm că jucătorii sunt numerotaţi de la $1$ la $K$. Pe următoarele $L-2$ linii sunt descrise în ordine acţiunile asociate cerculeţelor $2, 3, \dots, L-1$, câte o acţiune pe o linie, sub forma a două numere naturale $C \ P$ separate prin spaţiu.

Dacă $C=1$ şi $P>0$ pionul ajuns în acest cerculeţ va avansa cu $P$ cerculeţe (dacă $P$ este mai mare decât numărul de cerculeţe existente până la cerculeţul final, pionul va rămâne în cerculeţul final).
Dacă $C=1$ şi $P<0$ atunci pionul ajuns în acest cerculeţ va merge înapoi cu $-P$ cerculeţe (dacă $-P$ este mai mare decât numărul de cerculeţe existente până la cerculeţul de start, pionul va fi plasat în cerculeţul de start).
Dacă $C=1$ şi $P=0$, jucătorul trebuie să mai dea o dată cu zarul (adică pionul său va avansa cu următorul număr aleator din secvenţa de numere aleatoare generată).
Dacă $C=0$ atunci şi $P=0$ şi înseamnă că cerculeţul corespunzător nu are nici o acţiune asociată. $C$ poate avea doar valorile $0$ şi $1$.

Date de ieşire

Fişierul de ieşire piticot.out va conţine două linii; pe prima linie va fi scris un numărul jucătorului care câştigă jocul, iar pe cea de a doua linie numărul total de mutări efectuate în joc (ori de câte ori un pion este ridicat de pe tablă se consideră că s-a efectuat o mutare).

Restricţii şi precizări

• $0 \leq a, b, x_0 \leq 1 \ 000$
• $0 < c ≤ 1 \ 000$
• $1 \leq K, L ≤ 1 \ 000$
• Se garantează că jocul se termină.

Exemplu

piticot.in

1 1 100 1
2 6
0 0
1 -3
1 0
1 1

piticot.out

2
4

Explicație

$a=1, b=1, c=100, x_0=1$. Secvenţa de numere aleatoare generată este: $2, 3, 4, 5, 6, 7, 8, 9, \dots$
Iniţial toţi pionii jucătorilor sunt în cerculeţul $1$. Primul jucător dă cu zarul, obţine valoarea $2$ şi avansează în cerculeţul $3$ (mutare $1$). Deoarece acest cerculeţ are asociată o acţiune, jucătorul $1$ trebuie să execute acţiunea respectivă (se întoarce în cerculeţul de start - mutare $2$). Este rândul jucătorului $2$, acesta dă cu zarul, obţine valoarea $3$, ajunge în cerculeţul $4$ (mutare $3$), care are asociată o acţiune (jucătorul trebuie să mai dea o dată cu zarul, obţine valoarea $4$, avansează în cerculeţul final - mutare $4$ - şi câştigă jocul).