jstc

Jstc

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

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $jstc.in$ ...

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 in ordinea in care acestea sunt efectuate.
 
**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';

h2. Date de ieşire

În fişierul de ieşire $jstc.out$ ...

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

h2. Restricţii

h2. Restricţii si precizari
 
* $1 ≤ A, B ≤ 10^9^$
* Numarul de operatii de tip 'I' din fisier nu va depasi $10$^6^
* Pentru $30%$ din teste numarul de operatii de tip 'I' nu va depasi $10^5^$
* Se garanteaza ca niciodata nu va aparea o operatie de tip 'E' cand stiva este goala
* Se garanteaza ca prima operatie din fisier este de tipul 'I'
* 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$
* Din cauza numarul mare de caractere ce trebuiesc citite, se recomanda ca intreg sirul de comenzi sa fie citit deodata si nu caracter cu caracter

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. jstc.in |_. jstc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 2
IIEIQIEIIIQIEEEQQQ
| 11

|
h3. Explicaţie

...

Pentru fiecare operatie Q, stiva, X si raspunsurile vor fi (numerele ingrosatre reprezinta $NRI[k]$):
 
# stiva = $(1, 3)$, $X[ 1 ] = (3 * 0 + 2) % **3** + 1 = 3 => rez = 3$
# stiva = $(1, 3, 5, 6, 7)$, $X[ 2 ] = (3 * 3 + 2) % **7** + 1 = 5 => rez = 5$
# stiva = $(1, 3, 5)$, $X[ 3 ] = (3 * 5 + 2) % **8** + 1 = 2 => rez = 3$
# stiva = $(1, 3, 5)$, $X[ 4 ] = (3 * 2 + 2) % **8** + 1 = 1 => rez = 1$
# stiva = $(1, 3, 5)$, $X[ 5 ] = (3 * 1 + 2) % **8** + 1 = 6 => rez = -1$
 
suma afisata este $3 + 5 + 3 + 1 + (-1) = 11$

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

3472