Pikimad teed puus

문제

Jaak ja Jaagup osalesid ühel programmeerimisvõistlusel tiimina, teenisid suure koguse ˇsokolaadi ja tahavad selle omavahel ära jagada. Mõlemad on küllalt ülbed ja kumbki arvab, et tema panus tiimi edukusse oli suurem kui teise oma.

Nad mõtlesid ˇsokolaadi jagamiseks välja susteemi, mis tundus m ¨ õlemale õiglane. Nimelt esitavad nad üksteisele kordamööda informaatikaülesandeid. Teine peab esitatud ülesande võimalikult kiiresti ja elegantselt ära lahendama ja siis võrreldakse lahendamise aega ja elegantsust ülesande esitaja omadega. Šokolaad jagatakse vastavalt sellele, kumb on teise ülesannete lahendamisel edukam.

Jaagup esitas Jaagule järgmise ülesande:

On antud puu, mille N tippu on tähistatud 1, 2, . . . , N. Lisaks on puu igal serval e kaal w(e). Puu kohta esitatakse Q päringut kujul:

1. Sea tipust i selle ülemusse minema serva uueks kaaluks w'
2. Leia tipu i alampuus tipust i väljuvate lihtsate teede kaalude maksimum. Tee kaaluks nimetame kõigi teele jäävate servade kaalude summat. Lihtsaks nimetame teed, mis ei läbi uhtki tippu korduvalt.

Jaak jäi selle ülesandega hätta ja otsustas abi küsida. Lahendada Jaagule antud ülesanne ära.

입력

Tekstifaili esimesel real on täisarv N (1 ≤ N ≤ 10⁵). Teisel real on N täisarvu x₁, x₂, . . . , x_N, kus x_i tähistab tipu i ülemust (kui i on puu juur, siis x_i = 0). Kolmandal real on N täisarvu w₁, w₂, . . . , w_N, kus w_i on tipu i ja selle ülemuse vahel oleva serva esialgne kaal (−10⁹ ≤ w_i ≤ 10⁹, i ∈ 1 . . . N).

Neljandal real on täisarv Q (1 ≤ Q ≤ 10⁵). Järgmisel Q real on igaühel esimesena täisarv T (1 ≤ T ≤ 2), mis tähistab operatsiooni tüüpi, ja vastavalt sellele kas täisarvud i (1 ≤ i ≤ N) ja w' (−10⁹ ≤ w' ≤ 10⁹) või lihtsalt täisarv i.

출력

Tekstifaili väljastada 2. tüüpi päringute vastused, igaüks eraldi reale, päringute sisendis esinemise järjekorras.