kthvalue

Kth Value

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

Poveste şi cerinţă...

Aveti o problema foarte simpla de rezolvat. Vi se da un sir (initial vid) si multe operatii pe el.
 
Operatiile sunt de $5$ tipuri:
 
* Tipul $1$, se adauga pe pozitia 1 valoarea $v$, celelalate elemente deplasandu-se cu $1$ la dreapta.
* Tipul $2$, se adauga la final valoarea $v$
* Tipul $3$, se sterge primul element, iar restul se deplaseaza cu $1$ la stanga, inversa operatiei de tip $1$
* Tipul $4$, se sterge ultimul element, inversa operatiei de tip $2$
* Tipul $5$, vi se dau un $x$, $y$ si un $k$. Trebuie sa spuneti care este al $k$-lea element in ordinea sortari printre elemente aflate pe pozitiile $x$, $x + 1$, $x + 2$, ..., $y$ din sir.

h2. Date de intrare

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

Fişierul de intrare $kthvalue.in$ va contine pe prima linia un numar natural $M$, reprezentand numarul de operatii pe care trebuie sa le sustineti.
Urmatoarele $M$ linii vor descrie fiecare operatie in parte. Astfel primul numar de pe fiecare linie va reprezenta tipul operatiei (1 2 3 4 sau 5).
 
* Pentru operatiile de tip 1 pe acelasi rand se va mai afla un numar $x$ reprezentand valoarea ce va fi adaugata.
* Pentru operatiile de tip 5 pe acelasi rand se vor mai afla $3$ numere $x$, $y$ si $k$ cu descrierile de mai sus.

h2. Date de ieşire

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

În fişierul de ieşire $kthvalue.out$ trebuie sa se afle atatea linii cate operatii de tip 5 sunt. Pentru fiecare trebuie sa afisati numarul corespunzator.

h2. Restricţii

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

* $1 ≤ M ≤ 1.000.000$
* $1 ≤ x ≤ y ≤ numarul de elemente din sir la momentul respectiv$
* $1 ≤ v ≤ M$
* $Nu vor fi operatii de tip 3 sau 4 cand sirul este vid$

h2. Exemplu