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.

* 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 nu mai poate sa isi raspunda la intrebari. Ajutati-l!!!

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!!!

h2. Date de intrare

Fisierul de intrare va fi formatat astfel:
Pe prima linie doua numere naturale $A$ si $B$.

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)

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)

h2. Date de ieşire

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

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

h2. Restricţii si precizari

* $1 <= A, B <= 10^9$
* Numarul de operatii de tip 'I' din fisier nu va depasi $10$^6^

* 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$

* 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

h2. Exemplu

h3. Explicaţie
Pentru fiecare operatie Q, stiva, X, si raspunsul vor fi:

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$ = $1$ => rez = $-1$
suma afisata este $3 + 5 + 3 + 1 + (-1) = 11$

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 = 1 => rez = -1
suma afisata este 3 + 5 + 3 + 1 + (-1) = 11

== include(page="template/taskfooter" task_id="jstc") ==