FMI NO STRESS 12 | insert1insert2

Fie șirul $V$, indexat de la $0$, inițial vid. Pe acesta se efectuează următoarele tipuri de operații:

• 1 p val — se inserează un element roșu la poziția $p$ cu valoarea $val$
• 2 p val — se inserează un element negru la poziția $p$ cu valoarea $val$
• 3 — se calculează suma elementelor dintre poziția ultimului element roșu inserat și poziția ultimului element negru inserat

Se garantează că toate operațiile sunt valide: $p$ este mai mic sau egal decât lungimea curentă a șirului, iar o operație de tipul $3$ se va efectua doar după ce șirul conține cel puțin un element roșu și cel puțin un element negru.

Cerință

Să se afișeze suma tuturor valorilor calculate de operațiile de tip $3$, modulo $666013$.

Date de intrare

Pe prima linie se găsește un număr natural $Q$, ce reprezintă numărul de operații efectuate. Următoarele $Q$ linii reprezintă, în ordine, operațiile efectuate. Primul element de pe fiecare linie reprezintă tipul ei (1, 2 sau 3). Dacă tipul unei operații este $1$ sau $2$, pe acea linie se regăsesc și valorile $p$ și $val$.

Date de ieșire

Să se afișeze restul împărțirii la $666013$ a sumei tuturor valorilor calculate la operațiile de tip $3$.

Restricții și precizări

• $1 \leq Q \leq 200 \ 000$;
• $1 \leq val \leq 10^9$;
• Sumele calculate în cadrul operațiilor de tip $3$ includ și capetele subsecvențelor;
• Pentru teste în valoare de $36$ de puncte, $1 \leq Q \leq 10 \ 000$;
• Pentru restul de $64$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

6
1 0 1
1 0 2
2 1 3
3
2 0 4
3

stdout

11

Explicație

1 0 1   =>  V = [1]
1 0 2	=>  V = [2, 1]
2 1 3	=>  V = [2, 3, 1]
3		=>  S += 5
2 0 4	=>  V = [4, 2, 3, 1]
3		=>  S += 6