Fişierul intrare/ieşire:	jstc.in, jstc.out	Sursă	Algoritmiada 2009, Runda 1
Autor	Cosmin Gheorghe	Adăugată de	Gheorghe Cosmin •gcosmin
Timp execuţie pe test	0.8 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Jstc

Angelinei ii place sa se joace cu stive. Ea are o stiva initial vida pe care efectueaza mai multe tipuri de operatii:

• Operatie de tip insert. La a k-a operatie de tip insert se insereaza al k-lea numar natural nenul la sfarsitul stivei.
• Operatie de tip erase. La operatia de tip erase se sterge ultimul element adaugat in stiva.
• Operatie de tip query. Angelina se gandeste la un numar X si se intreaba care este cel mai mic numar din stiva mai mare sau egal ca numarul X.

Pentru ca Angelina are foarte mult timp liber, face prea multe operatii pe stiva si realizeaza ca nu mai poate sa isi raspunda la intrebari. De aceea va roaga pe voi sa o ajutati.

Date de intrare

Fisierul de intrare jstc.in va contine pe prima linie doua numere naturale A si B. Pe a doua linie se afla un sir de caractere 'I', 'E', sau 'Q' ce reprezinta operatiile de tip insert, erase si respectiv query.

Numerele X pentru operatiile query se vor determina in urmatorul mod:

• Se considera X[ 0 ] = 0;
• A k-a operatie de tip 'Q' (query) din fisier se calculeaza astfel: X[ k ] = (A * X[k - 1] + B) % NRI[ k ] + 1;
• NRI[ k ] = numarul de operatii de tip 'I' (insert) ce au aparut inaintea celei de a k-a operatie de tip 'Q';

Date de ieşire

Singura linie din fisierul de iesire compact.out va contine un singur numar si anume suma raspunsurilor intrebarilor Angelinei.

Restricţii si precizari

• 1 <= A, B <= 10⁹
• Numarul de operatii de tip 'I' din fisier nu va depasi 10⁶
• Pentru 30% din teste numarul de operatii de tip 'I' nu va depasi 10⁵
• Se garanteaza ca niciodata nu va aparea o operatie de tip 'E' cand stiva este goala
• Numarul total de operatii din fisier nu depasteste 10⁷
• Daca pentru o operatie de tip 'Q' nu exista un element in stiva mai mare sau egal cu X raspunsul va fi -1

Exemplu

Explicaţie

Pentru fiecare operatie Q, stiva, X si raspunsurile vor fi (numerele ingrosatre reprezinta NRI[k]):

1. stiva = (1, 3), X[ 1 ] = (3 * 0 + 2) % 3 + 1 = 3 => rez = 3
2. stiva = (1, 3, 5, 6, 7), X[ 2 ] = (3 * 3 + 2) % 7 + 1 = 5 => rez = 5
3. stiva = (1, 3, 5), X[ 3 ] = (3 * 5 + 2) % 8 + 1 = 2 => rez = 3
4. stiva = (1, 3, 5), X[ 4 ] = (3 * 2 + 2) % 8 + 1 = 1 => rez = 1
5. stiva = (1, 3, 5), X[ 5 ] = (3 * 1 + 2) % 8 + 1 = 6 => rez = -1

suma afisata este 3 + 5 + 3 + 1 + (-1) = 11

Cum se trimit solutii?