valutar

Valutar este un joc care poate fi jucat de oricâţi jucători. La începutul jocului, fiecare jucător primeşte $L$ lei şi $E$ euro, precum şi un jeton numerotat cu numărul jucătorului. Mai exact, dacă există $M$ jucători, vor fi $M$ jetoane, numerotate de la $1$ la $M$.
Tabla de joc este harta unui oraş pe care este ilustrat un traseu circular ce conţine $N$ case de schimb valutar, numerotate în ordinea de pe traseu de la $1$ la $N$. Fiind circular, după casa $N$ urmează casa $1$. Pentru fiecare casă de schimb valutar se cunosc două valori $C$ şi $V$ ($C$ reprezintă câţi lei plăteşte un jucător dacă vrea să cumpere $1$ euro de la casa respectivă, iar $V$ reprezintă câţi lei primeşte jucătorul dacă vrea să vândă $1$ euro). Fiecare casă are o anumită culoare în funcţie de care jucătorul ajuns în punctul respectiv trebuie să efectueze o anumită acţiune astfel:

Iniţial toţi jucătorii pornesc de la casa de schimb valutar $1$ care este albă. Există $N$ case de schimb valutar și $M$ jucători. Jucătorii mută pe rând în ordinea jetoanelor. Mai întâi mută jucătorul $1$, apoi $2, 3, \dots, M$. După jucătorul $M$ va muta din nou $1$ etc. La o mutare, un jucător care nu a fost eliminat din joc:

• „dă” cu zarul electronic; zarul va afişa un număr întreg $nr$;
• avansează cu $nr$ poziţii (adică dacă jetonul său este la casa $i$ va ajunge la casa $i+nr$);
• execută acţiunea asociată casei de schimb valutar în care a ajuns, în funcţie de culoarea acesteia.

Zarul electronic funcţionează astfel: la mutarea cu numărul $j$ este generat numărul $nr_j$ calculat după formula $nr_j = (a \cdot nr_{j-1}+b)\ \%\ N+1$, unde $nr_{j-1}$ este numărul generat la mutarea $j-1$; $a, b$ şi $nr_0$ sunt trei valori cunoscute, iar $\%$ reprezintă restul împărţirii întregi (mod).

Cerință

Scrieţi un program care să rezolve următoarele cerinţe:

• determină numărul de jucători existenţi în joc după $X$ mutări;
• determină jucătorul care a rămas în joc şi care are cea mai mare sumă de Euro după $X$ mutări.

Date de intrare

Fişierul de intrare valutar.in conţine pe prima linie cerinţa care trebuie să fie rezolvată ($1$ sau $2$).
Pe a doua linie se află numerele naturale $a, b$ şi $nr_0$, cu semnificaţia din enunţ.
Pe a treia linie se află numerele naturale $N, M, L, E, X$, reprezentând numărul de case de schimb valutar, numărul de jucători, câţi lei şi câţi euro primeşte fiecare jucător la începutul jocului, respectiv numărul de mutări din joc. Pe următoarele $N$ linii sunt descrise casele de schimb valutar, câte o casă pe o linie, în ordinea de la $1$ la $N$, sub forma $Cod \ C \ V$, cu semnificaţiile din enunţ. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire valutar.out va conţine o singură linie. Dacă cerinţa este $1$, linia va conţine un număr natural reprezentând numărul de jucători existenţi în joc după $X$ mutări. Dacă cerinţa este $2$, linia va conţine numărul jetonului jucătorului rămas în joc şi care are cea mai mare sumă de euro după $X$ mutări.

Restricții și precizări

• $1 \leq M, C, V \leq 100$;
• $1 \leq a, b, nr_0, N, X \leq 10 \ 000$;
• $1 \leq L, E \leq 10^6$;
• Toate casele de schimb valutar au suficienţi lei şi euro pentru efectuarea oricărei acţiuni.
• Se garantează că pentru datele de test la cerinţa $2$ va rămâne în joc după $X$ mutări un singur jucător cu suma maximă de euro.
• Pentru fiecare cerinţă se acordă $50$% din punctajul obţinut pe teste.

Exemplul 1

valutar.in

1
3 2 7
5 3 2 3 8
A 1 1
G 5 4
G 6 4
V 6 5
R 2 3

valutar.out

1

Exemplul 2

valutar.in

2
3 2 7
5 3 2 3 8
A 1 1
G 5 4
G 6 4
V 6 5
R 2 3

valutar.out

2

Explicații

Numerele care se obţin când se dă cu zarul se generează astfel: $nr_j = (3 \cdot nr_{j-1}+2)$, unde $nr_0=7$. Există în joc $5$ case de schimb valutar şi $3$ jucători. Toţi jucătorii au iniţial $2$ lei şi $3$ euro şi se află la casa de schimb valutar $1$ care este albă. Se efectuează $8$ mutări astfel: