Annettuna on juurellinen puu, jossa on n solmua. Solmut on numeroitu 1,2,\ldots,n, ja solmu 1 on juuri. Lisäksi kullakin solmulla on arvo.

Tehtäväsi on käsitellä seuraavia kyselyitä:

1. muuta solmun s arvoa
2. laske summa polulla juuresta solmuun s

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: solmujen määrä ja kyselyiden määrä.

Seuraavalla rivillä on n kokonaislukua v_1,v_2,\ldots,v_n: kunkin solmun arvo.

Sitten syötteessä on n-1 riviä, jotka kuvaavat puun kaaret. Jokaisella rivillä on kaksi kokonaislukua a ja b: solmujen a ja b välillä on kaari.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokainen kysely on muotoa "1 s x" (muuta solmun s arvoksi x) tai "2 s" (laske summa polulla juuresta solmuun s).

Tuloste

Tulosta vastaus jokaiseen kyselyyn tyyppiä 2.

Rajat

• 1 \le n,q \le 10^5
• 1 \le v_i \le 10^9
• 1 \le a, b, s \le n
• 1 \le x \le 10^9

Esimerkki

Syöte:

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4

Tuloste:

11
8