Roata Norocului

„Roata norocului... când ești sus sau când ești jos, soarta este mereu schimbătoare, precum clasamentul de alaltăieri.” — Un mare gânditor f̵r̵a̵n̵c̵e̵z̵ japonez.

Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$. Rădăcina arborelui este fixată în nodul $1$. Fiecare nod $u$ are o valoare $a_u$, care este un număr natural. Pentru că nu ne plac arborii, putem să reducem arborele la un singur nod, aplicând următoarea operație de $N −1$ ori:

• Se aleg oricare două noduri distincte unite printr-o muchie, $u$ și $v$
• Se adaugă contorului $S$ valoarea $|a_u − a_v |$. Valoarea inițială a contorului $S$ este $0$;
• Cele două noduri se unesc. Prin unire înțelegem ștergerea celor două noduri din arbore și crearea unui nod nou $w$, pentru care $a_w = min(a_u, a_v)$.

Toate muchiile incidente cu $u$ și $v$ își schimbă capătul egal cu $u$ sau $v$ în $w$, mai puțin muchia $(u, v)$, care dispare.

Costul total al celor $N − 1$ operații este valoarea lui $S$ după efectuarea acestora.

Cerință

Se dau $Q$ interogări de tipul:

• 1 u x: Valoarea nodului $u$ devine egală cu $x$
• 2 u: Se cere costul total minim al unui șir de operații valid care reduce subarborele nodului $u$ la un singur nod. Amintim că rădăcina arborelui este fixată în nodul $1$.

Date de intrare

Pe prima linie a intrării se află un număr natural $N$, reprezentând numărul de noduri din arbore.

Pe a doua linie sa află $N$ numere naturale, al $i$-lea număr reprezentând valoarea ai asociată nodului $i$ din arbore, unde $i$ este un număr de la $1$ la $N$.

Pe a treia linie se află $N − 1$ numere naturale, al $i$-lea număr reprezentând părintele nodului $i + 1$ din arbore, undei este un număr de la $1$ la $N −1$ (nodul $1$ nu are părinte, fiind rădăcina arborelui).

Pe a patra linie se află un număr natural $Q$, reprezentând numărul de interogări. Pe următoarele $Q$ linii se află interogările în formatul descris în enunț, câte una pe fiecare linie.

Date de ieșire

Ieșirea trebuie să conțină câte un răspuns pe linie corespunzând fiecărei interogări de tipul $2$, în ordinea în care acestea au fost date.

Restricții și precizări

• $1 ≤ N ≤ 200 \ 000$
• $1 ≤ Q ≤ 200 \ 000$
• $1 ≤ a_i ≤ 10^9$ pentru $1 ≤ i ≤ N$
• $1 ≤ x ≤ 10^9$ pentru fiecare interogare de tipul $1$.

Exemplul 1

stdin

7
4 7 9 7 4 1 2
1 1 3 2 3 2
1
2 1

stdout

11

Exemplul 2

stdin

7
6 6 5 1 6 6 4
1 1 2 3 3 3
3
2 1
1 1 1
2 1

stdout

7
11