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

Poveste şi cerinţă...

Tractorel s-a gândit un pic, pic la o problemă în timp ce ploua cu adrese intr-o dimineaţă. El se gândeşte serios la un şir de $N$ numere întregi având la stânga dolărei şi la dreapta leii grei. Deoarece Tractorel deţine puteri supranaturale, el poate efectua următoarele operaţii asupra şirului:
 
* $Insert (X Y)$ – inserează în şir elementul cu valoarea $Y$ după elementul de pe poziţia $X$ (dacă $X$ este $0$, $Y$ se inserează la inceputul şirului)
* $Delete K$ – se elimină elementul de pe poziţia $K$ din şir
* $Query$
 
Tractorel consideră că un şir are proprietea de Minune dacă toate elementele şirului de sume parţiale care încep de la primul element sunt nenegative. La operaţia de tip $Query$, Tractorel vă roagă frumos să determinaţi o permutare circulară a şirului astfel încât acesta să aibă proprietatea de Minune. Spre exemplu, dacă avem şirul $S = [1, -1, 2, 5]$ acesta se poate permuta circular in şirurile $S0 = [1, -1, 2, 5]$,  {$S1 = [-1, 2, 5, 1]$},  {$S2 = [2, 5, 1, -1]$}, $S3 = [5, 1, -1, 2]$ iar şirul sumelor parţiale asociat acestor şiruri este: $S0’ = [1, 0, 2, 7]$, $S1’ = [-1, 1, 6, 7]$, $S2’ = [2, 7, 8, 7]$, $S3’ = [5, 6, 5, 7]$. Se observă că şirurile $S0$, $S2$, $S3$ respectă proprietatea de şiruri Minune.
 
Tractorel, fiind modest, nu doreşte decât afişarea unui singur număr la operaţia de tip $Query$, anume cu câte poziţii trebuie să permute circular şirul $S$ spre stânga pentru ca acesta să aibă proprietatea de şir Minune. Un răspuns corect la o operaţie $Query$ pe $S = [1, -1, 2, 5]$ este $3$ pentru că şirul obţinut prin permutarea circulară a lui $S$ de $3$ ori la stânga este $S3$, care este un şir Minune.
 
În caz că nu există nici un şir minune în toate permutările circulare ale şirului, se va afişa $-1$.
 
h2. Cerinţă
 
Pentru un şir conţinând iniţial $N$ numere întregi şi $M$ operaţii de tipul $Insert (X Y)$, $Delete K$, $Query$. personajul principal doreşte să afişati răspunsul la toate intrebările de tip $Query$.

h2. Date de intrare

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

În fişierul de intrare $rotatii.in$, pe prima linie se află $2$ numere intregi $N$ şi $M$, iar pe a $2$-a linie se află $N$ numere intregi. După linia $2$ urmează $M$ linii, reprezentând operaţiile codificate in felul următor:
 
* $0 X Y – Insert (X, Y)$
* $1 K – Delete$
* $2 – Query$

h2. Date de ieşire

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

În fişierul de ieşire $rotatii.out$ se va afişa raspunsul la fiecare query câte un număr pe linie reprezentând numărul de poziţii cu care trebuie rotit şirul sau $-1$ dacă nu există soluţie.

h2. Restricţii

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

* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 100000$
* $0 ≤ X, K ≤ numărul curent de elemente din şir$
* Şirul conţine numere întregi din intervalul $[-10^9^, 10^9^]$

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

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

| 4 6
2 -3 5 2
0 4 -100
2
1 5
2
0 1 -4
2
| -1
3
3

|
h3. Explicaţie

...

La primul query sirul are forma $2 -3 5 2 -100$ şi pentru nicio permutare circulară nu avem proprietatea de şir Minune. Mai departe analizaţi :).

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

9053