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

Lui Gigel ii place sa se joace cu stive. El 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 in stiva cel de-al k-lea numar natural nenul.
• Operatie de tip erase. Operatia de tip erase se sterge ultimul element adaugat in stiva
• Operatie de tip query. Gigel se gandeste la un numar X si se intreaba care este cel mai mic numar ce se afla in stiva mai mare sau egal ca numarul x

Pentru ca Gigel are timp fara numar la dispozitie face prea multe operatii pe stiva si realizeaza ca numai poate sa isi raspunda la intrebari. Ajutati-l!!!

Date de intrare

Fisier de intrare va fi formatat astfel:
Pe prima linie doua numere naturale A si B.
Pe a doua linie 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 pana la a k-a operatie de tip 'Q' (query)

Date de ieşire

Singura linie din fisierul de iesire va contine un singur numar si anume suma raspunsurilor intrebarilor lui gigel

Restricţii si precizari

• 1 <= A, B <= 10^9
• Numarul de operatii de tip 'I' din fisier nu va depasi 10^6
• 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^7
• 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 raspunsul vor fi:
1. stiva = (1, 3), X¹ = 3 => rez = 3
2. stiva = (1, 3, 5, 6, 7), X² = 5 => rez = 5
3. stiva = (1, 3, 5), X³ = 2 => rez = 3
4. stiva = (1, 3, 5), X⁴ = 1 => rez = 1
5. stiva = (1, 3, 5), X⁵ = 6 => rez = -1
suma afisata este 3 + 5 + 3 + 1 + (-1) = 11

Cum se trimit solutii?