Problem 911: valutar

Valutar este un joc care poate fi jucat de oricâţi jucători. La începutul jocului, fiecare jucător primeşte $L$ lei şi $E$ euro, precum şi un jeton numerotat cu numărul jucătorului. Mai exact, dacă există $M$ jucători, vor fi $M$ jetoane, numerotate de la $1$ la $M$ .
Tabla de joc este harta unui oraş pe care este ilustrat un traseu circular ce conţine $N$ case de schimb valutar, numerotate în ordinea de pe traseu de la $1$ la $N$ . Fiind circular, după casa $N$ urmează casa $1$ . Pentru fiecare casă de schimb valutar se cunosc două valori $C$ şi $V$ ( $C$ reprezintă câţi lei plăteşte un jucător dacă vrea să cumpere $1$ euro de la casa respectivă, iar $V$ reprezintă câţi lei primeşte jucătorul dacă vrea să vândă $1$ euro). Fiecare casă are o anumită culoare în funcţie de care jucătorul ajuns în punctul respectiv trebuie să efectueze o anumită acţiune astfel:

Culoare	Cod	Efect
Alb	A	Jucătorul nu face nimic la această mutare.
Roşu	R	Jucătorul primeşte un cartonaş denumit „pas”. Un jucător care are un cartonaş pas va folosi ulterior cartonaşul (o singură dată, după care cartonaşul va fi scos din joc) şi astfel evită să execute o acţiune pe care nu poate să o execute, pentru a nu fi eliminat din joc.
Galben	G	Jucătorul trebuie să cumpere $i$ euro (unde $i$ este numărul casei de schimb valutar la care se află). Dacă nu are suficienţi lei pentru a face acest lucru şi nu deţine un cartonaş pas, jucătorul este eliminat din joc. Dacă are un cartonaş pas, jucătorul îl va folosi şi nu va executa acţiunea, fără a fi eliminat din joc.
Verde	V	Jucătorul trebuie să vândă $i$ euro (unde $i$ este numărul casei de schimb valutar la care se află). Dacă nu are suficienţi euro pentru a face acest lucru şi nu deţine un cartonaş pas, jucătorul este eliminat din joc. Dacă are un cartonaş pas, jucătorul îl va folosi şi nu va executa acţiunea, fără a fi eliminat.

Iniţial toţi jucătorii pornesc de la casa de schimb valutar $1$ care este albă. Există $N$ case de schimb valutar și $M$ jucători. Jucătorii mută pe rând în ordinea jetoanelor. Mai întâi mută jucătorul $1$ , apoi $2, 3, \dots, M$ . După jucătorul $M$ va muta din nou $1$ etc. La o mutare, un jucător care nu a fost eliminat din joc:

„dă” cu zarul electronic; zarul va afişa un număr întreg $nr$ ;
avansează cu $nr$ poziţii (adică dacă jetonul său este la casa $i$ va ajunge la casa $i+nr$ );
execută acţiunea asociată casei de schimb valutar în care a ajuns, în funcţie de culoarea acesteia.

Zarul electronic funcţionează astfel: la mutarea cu numărul $j$ este generat numărul $nr_j$ calculat după formula $nr_j = (a \cdot nr_{j-1}+b)\ \%\ N+1$ , unde $nr_{j-1}$ este numărul generat la mutarea $j-1$ ; $a, b$ şi $nr_0$ sunt trei valori cunoscute, iar $\%$ reprezintă restul împărţirii întregi (mod).

Cerință

Scrieţi un program care să rezolve următoarele cerinţe:

determină numărul de jucători existenţi în joc după $X$ mutări;
determină jucătorul care a rămas în joc şi care are cea mai mare sumă de Euro după $X$ mutări.

Date de intrare

Fişierul de intrare valutar.in conţine pe prima linie cerinţa care trebuie să fie rezolvată ( $1$ sau $2$ ).
Pe a doua linie se află numerele naturale $a, b$ şi $nr_0$ , cu semnificaţia din enunţ.
Pe a treia linie se află numerele naturale $N, M, L, E, X$ , reprezentând numărul de case de schimb valutar, numărul de jucători, câţi lei şi câţi euro primeşte fiecare jucător la începutul jocului, respectiv numărul de mutări din joc. Pe următoarele $N$ linii sunt descrise casele de schimb valutar, câte o casă pe o linie, în ordinea de la $1$ la $N$ , sub forma $Cod \ C \ V$ , cu semnificaţiile din enunţ. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire valutar.out va conţine o singură linie. Dacă cerinţa este $1$ , linia va conţine un număr natural reprezentând numărul de jucători existenţi în joc după $X$ mutări. Dacă cerinţa este $2$ , linia va conţine numărul jetonului jucătorului rămas în joc şi care are cea mai mare sumă de euro după $X$ mută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 suficienţi lei şi euro pentru efectuarea oricărei acţiuni.
Se garantează că pentru datele de test la cerinţa $2$ va rămâne în joc după $X$ mutări un singur jucător cu suma maximă de euro.
Pentru fiecare cerinţă se acordă $50$ % din punctajul obţinut pe teste.

Exemplul 1

valutar.in

valutar.out

Exemplul 2

valutar.in

valutar.out

Explicații

Numerele care se obţin când se dă cu zarul se generează astfel: $nr_j = (3 \cdot nr_{j-1}+2)%5+1$ , unde $nr_0=7$ . Există în joc $5$ case de schimb valutar şi $3$ jucători. Toţi jucătorii au iniţial $2$ lei şi $3$ euro şi se află la casa de schimb valutar $1$ care este albă. Se efectuează $8$ mutări astfel:

Mutare	Jucător	nr	De unde pleacă	Unde ajunge	Acţiune	Lei	Euro	Observații
1	1	4	1	5	R	2	3	A primit un cartonaş pas
2	2	5	1	1	A	2	3	Nu face nimic
3	3	3	1	4	V	2	3	Trebuie să vândă $4$ euro, dar nu are decât $3$ , nu are cartonaş pas, deci este scos din joc.
4	1	2	5	2	G	2	3	Trebuie să cumpere $2$ euro, care costă $2 \cdot 5 = 10$ lei, el nu are destui bani, dar are un cartonaş pas pe care îl foloseşte, deci rămâne în joc
5	2	4	1	5	R	2	3	A primit un cartonaş pas
6	1	5	2	2	G	2	3	Trebuie să cumpere $2$ euro, care costă $2 \cdot 5 = 10$ lei, el nu are destui bani, nu mai are niciuun cartonaş, deci este eliminat din joc
7	2	3	5	3	G	2	3	Trebuie să cumpere $3$ euro care ar costa $6 \cdot 3 = 18$ lei, nu are bani dar are un cartonaş pas pe care îl foloseşte şi nu este eliminat din joc
8	2	2	3	5	R	2	3	Primeşte un cartonaş pas

valutar