insert1insert2

Time limit: 0.3s Memory limit: 64MB Input: Output:

Fie șirul VV, indexat de la 00, 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 pp cu valoarea valval
  • 2 p val — se inserează un element negru la poziția pp cu valoarea valval
  • 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: pp este mai mic sau egal decât lungimea curentă a șirului, iar o operație de tipul 33 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 33, modulo 666013666013.

Date de intrare

Pe prima linie se găsește un număr natural QQ, ce reprezintă numărul de operații efectuate. Următoarele QQ 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 11 sau 22, pe acea linie se regăsesc și valorile pp și valval.

Date de ieșire

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

Restricții și precizări

  • 1Q200 0001 \leq Q \leq 200 \ 000;
  • 1val1091 \leq val \leq 10^9;
  • Sumele calculate în cadrul operațiilor de tip 33 includ și capetele subsecvențelor;
  • Pentru teste în valoare de 3636 de puncte, 1Q10 0001 \leq Q \leq 10 \ 000;
  • Pentru restul de 6464 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

Log in or sign up to be able to send submissions!