Vasile

Time limit: 1.5s Memory limit: 1024MB Input: Output:

Banii mulți se fac ușor, banii puțini se fac greu.
--- 'Claus

Vasile este prietenul Linei. Recent, Vasile și-a făcut un cont de Pinance pentru a petrece mai mult timp investind în criptomonede decât la biserică. Surpriza lui a venit într-o zi când, fără vreun motiv aparent, a observat că investițiile lui au dat roade. Surprins de acest eveniment, a decis să analizeze evenimentele ce au avut loc în Plockchain care l-au adus la aceste culmi. Vasile ne-a explicat că ne putem imagina că Plockchain-ul funcționează în felul următor:

La început, în sistem există NN cereri de tranzacții, indexate de la 11 la NN, a ii-a din ele având un comision la efectuare de WiW_i și o unică altă cerere de care este direct dependentă PiP_i. Se spune că cererea cu indexul 11 era primordială sistemului și nu are nicio dependență. Vasile a observat mișcările din Plockchain și le-a clasificat în trei tipuri:

  1. Apare o nouă cerere cu comision inițial CC, a cărei dependență directă este TT. Indexul acestei cereri va fi N+t+1N + t + 1, unde tt este numărul de cereri adăugate anterior prin acest procedeu. Astfel, prima cerere adăugată are indexul N+1N + 1.
  2. Este modificat comisionul unei cereri cu index aa din WaW_a în CC.
  3. Este ștearsă complet din registru cererea cu index aa. Se garantează că nu există o altă cerere jj astfel încât Pj=aP_j = a (nu depindea nicio cerere de aa).

Lina, uimită de explicațiile lui Vasile, a început să se întrebe adesea de-a lungul acestor modificări următoarea întrebare:

Considerând toate cererile care există acum în sistem, cu ce comision ar fi răsplătit un hacker dacă ar efectua toate cererile care se află la cel mult HH dependențe în jos față de o cerere XX?

Spunem că o cerere AA se află la cel mult xx dependențe în jos față de BB dacă și numai dacă x0x \ge 0 și A=BA = B, sau x1x \ge 1 și PAP_A se află la cel mult x1x - 1 dependențe în jos față de BB. Considerăm de asemenea că, în urma efectuării unor cereri, hackerul primește suma comisioanelor aferente cererilor. Desigur, întrebările Linei nu au niciun efect asupra sistemului, acesta rămânând la fel în urma acestei operații. Din vina sistemului robust al Plockchain-ului, HH este același în orice întrebare de-a Linei.

Cerință

Vasile știe că ziua Linei va fi curând, așa că s-a gândit să-i ofere cel mai bun cadou din lume: O listă de numere ce reprezintă răspunsurile la întrebările ei. Cu toate acestea, el este mult prea ocupat să o facă singur, așa că te-a delegat pe tine să le afli.

Date de intrare

Pe primul rând se află numerele NN, QQ și HH, reprezentând numărul de cereri din sistemul original, numărul de modificări explicate de Vasile sau întrebări de-ale Linei, și constanta HH din întrebările Linei.

Urmează pe al doilea rând NN numere, al ii-lea reprezentând WiW_i, comisionul inițial al cererii cu indexul ii.

Urmează pe al treilea rând N1N - 1 numere, al ii-lea reprezentând Pi+1P_{i+1}, cererea de care este direct dependentă cererea cu indexul i+1i + 1.

Urmează apoi QQ rânduri, primul număr de pe fiecare fiind tt, reprezentând tipul operației. Apoi:

  1. Dacă t=1t = 1, urmează CC și TT, reprezentând parametrii cererii nou apărute.
  2. Dacă t=2t = 2, urmează aa și MM, reprezentând indexul cererii a cărei comision se modifică respectiv valoarea în care se modifică.
  3. Dacă t=3t = 3, urmează aa, reprezentând indexul cererii care este acum ștearsă din sistem.
  4. Dacă t=4t = 4, urmează XX, reprezentând indexul cererii pentru care pune {\color{blue}Lina} întrebarea. \end{enumerate}

Date de ieșire

În urma fiecărei întrebări (operație cu t=4t = 4), se va afișa un singur număr, anume răspunsul la întrebarea {\color{blue}Linei} pentru sistemul curent.

Restricții și precizări

  • 2N200 0002 \le N \le 200 \ 000;
  • 1Q200 0001 \le Q \le 200 \ 000;
  • 1HN1 \le H \le N;
  • 0C,M1 000 000 0000 \le C, M \le 1 \ 000 \ 000 \ 000 pentru toate operațiile.
  • T<RT < R pentru toate operațiile de tipul t=1t = 1, unde cu RR am notat indexul cererii nou adăugate în urma operației.
  • 1Pi<i1 \le P_i < i și 0Wi10000000000 \le W_i \le 1\,000\,000\,000, pentru orice cerere inițială ii.
  • Se garantează că pentru orice operație cererile implicate in aceasta există la momentul efectuării operației.
  • Se garantează că nicio operație de tipul t=3t = 3 va fi efectuată asupra cererii cu numărul 11.
  • Se garantează că nicio operație de tipul t=3t = 3 va fi efectuată asupra unei cereri ii pentru care există la momentul efectuării un jj astfel încât Pj=iP_j = i.
# Punctaj Restricții
1 13 N,Q5 000N, Q \le 5 \ 000
2 11 Pi=i1P_i = i - 1, pentru 2iN2 \le i \le N, iar t=4t = 4 pentru orice operație
3 16 t=4t = 4 pentru orice operație
4 10 H=1H = 1
5 14 Pi=i1P_i = i - 1, pentru 2iN2 \le i \le N, iar t=2t = 2 sau t=4t = 4 pentru orice operație
6 10 Pi=i2P_i = \left\lfloor\frac{i}{2}\right\rfloor, pentru 2iN2 \le i \le N, iar t=2t = 2 sau t=4t = 4 pentru orice operație
7 26 Fără restricții suplimentare.

Exemplu

stdin

8 7 2
10 12 4 20 4 5 11 10
1 1 3 4 2 6 6
1 50 4
4 3
2 1 50
4 1
2 6 35
1 5 7
4 6

stdout

78
91
61

Explicație

Pentru prima interogare, cererile care sunt la 22 dependențe în jos față de cererea 33 sunt 33, 44, 99, 55 cu costurile 44, 2020, 5050, 44. Astfel, trebuie să afișăm 4+20+50+4=784 + 20 + 50 + 4 = 78.

Structura inițiala˘\text{Structura inițială}

Structura dupa˘ prima operație\text{Structura după prima operație}

Structura dupa˘ primele 3 operații\text{Structura după primele 3 operații}

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