rotatii

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 $S_0 = [1, -1, 2, 5]$, $S_1 = [-1, 2, 5, 1]$, $S_2 = [2, 5, 1, -1]$, $S_3 = [5, 1, -1, 2]$ iar șirul sumelor parțiale asociat acestor șiruri este: $S_0^{’} = [1, 0, 2, 7]$, $S_1^{’} = [-1, 1, 6, 7]$, $S_2^{’} = [2, 7, 8, 7]$, $S_3^{’} = [5, 6, 5, 7]$. Se observă că șirurile $S_0, S_2, S_3$ 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 $S_3$, 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$.

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.

Date de intrare

Î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

Date de ieșire

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

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 100 \ 000$
• $0 \leq X, K \leq$ numărul curent de elemente din șir
• Șirul conține numere întregi din intervalul $[-10^9, 10^9]$

Exemplu

rotatii.in

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

rotatii.out

-1
3
3

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 :).