Fişierul intrare/ieşire:	kthvalue.in, kthvalue.out	Sursă	Happy Birthday Infoarena 2014
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	1.65 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Kthvalue

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.

Date de intrare

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.

Date de ieşire

Î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.

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

Exemplu

Explicaţie

Sirul va arata asa in urma transformarilor [] -> [1] -> [8 1] -> [8 1 8] -> [1 8] -> [1 8 7]

Cum se trimit solutii?