25133번 - Grozne granice 다국어

문제

Države Europske Unije možemo zamisliti kao graf u kojem između svake dvije države postoji točno jedan put, tj. kao stablo. Države su označene brojevima od 1ドル$ do $n$ s time da je Hrvatska označena brojem 1ドル$. Kako ove godine Gospodin Malnar predsjeda Europskom unijom, potrebno je organizirati brojne sastanke. Predstavnici država su čudni te se jako vole kretati u grupama, stoga pri svom putovanju za Hrvatsku, prvo će se u svakoj državi sastati svi oni koji na svom putovanju prolaze kroz tu državu te će potom zajedno s predstavnikom te države nastaviti svoje putovanje kao grupa do sljedeće države, gdje će se opet spojiti zajedno s još predstavnika sve dok se svi zajedno ne nađu na sastanku u čvoru 1. (Za detaljnije objašnjenje pogledati objašnjenje prvog primjera.)

Nažalost, među državama Europske Unije uvedena je carina na ljude! Za svaku državu poznata je njezina carina $c_i$ te će svaka osoba morati platiti tu cijenu prilikom ulaska u državu, naravno predstavnici države ne plaćaju carinu u svojoj državi. No, carinici su cinični prema cijeloj ideji Europske Unije, pa su u svakoj državi odlučili najvećoj grupi ljudi koja zajedno dolazi naplatiti dvostruku cijenu, ako ima više jednako velikih grupa naplatit će onoj koja dolazi iz države s najmanjom oznakom. Promjene su u Europskoj Uniji burne pa vas je gospodin Malnar zamolio da podržite tri ključne operacije:

• 1ドル$ $v$ - kada bi se trenutno održao sastanak, koliko novaca bi morao platiti predstavnik države $v$
• 2ドル$ $v$ $c$ - država $v$ mijenja cijenu carine na $c$
• $ 3ドル $v$ $c$ - pojavila se nova država s oznakom $k,ドル $k$ je najmanji prirodan broj takav da ne postoji država s tom oznakom, koja ima carinu $c$ te je spojena na državu $v$

Gospodin Malnar izgubljen je među svim obavezama te vas moli da napravite program s kojim će moći brzo odgovarati na ova pitanja. Sljedeća dva tjedna su ključna!

입력

U prvom su retku brojevi $n$ i $q$ (1ドル ≤ n, q ≤ 10^5$) koji označavaju početni broj država te broj operacija.

U sljedećem retku nalazi se $n$ brojeva od kojih $i$-ti označava $c_i$ (0ドル ≤ c_i ≤ 10^9$), tj. carinu $i$-te države.

U sljedećih $n - 1$ redaka nalaze se brojevi $u_i$ te $v_i$ (1ドル ≤ u_i , v_i ≤ n,ドル $u_i \ne v_i$) koji označavaju da su države $u_i$ te $v_i$ spojene bridom.

Neka lastans označava odgovor na zadnju operaciju tipa 1ドル$ u nekom trenutku, odnosno $lastans = 0$ ako nije bilo operacija tipa 1ドル$. Neka je $k$ najveća oznaka neke države do tog trenutka. Neka $⊕$ označava bitovnu operaciju xor.

Ako je $i$-ti događaj tipa 1ドル,ドル onda se u retku nalaze brojevi 1ドル$ $v'$ (0ドル ≤ v' ≤ 10^{18},ドル 1ドル ≤ v ≤ $k) te je $v = v' ⊕ lastans$.

Ako je $i$-ti događaj tipa 2ドル,ドル onda se u retku nalaze brojevi 2ドル$ $v'$ $c'$ (0ドル ≤ v' , c' ≤ 10^{18},ドル 1ドル ≤ v ≤ k,ドル 0ドル ≤ c ≤ 10^9$) te je $v = v' ⊕ lastans,ドル $c = c' ⊕ lastans$.

Ako je $i$-ti događaj tipa 3ドル,ドル onda se u retku nalaze brojevi 3ドル$ $v'$ $c'$ (0ドル ≤ v' , c' ≤ 10^{18},ドル 1ドル ≤ v ≤ k,ドル 0ドル ≤ c ≤ 10^9$) te je $v = v' ⊕ lastans,ドル $c = c' ⊕ lastans$.

출력

Potrebno je u $i$-tom retku ispisati odgovor na $i$-tu operaciju tipa 1ドル$.

제한

힌트

Pojašnjenje prvog probnog primjera: Zato što je tek četvrta operacija prva tipa 1ドル,ドル $lastans = 0$ te operacija nije mijenjanja. Predstavnik države 2ドル$ putuje u državu 3ドル$ i plaća dvostruku carinu 6ドル$ zato što je jedina te stoga i najveća grupa koja ulazi u taj grad. Sada predstavnici iz gradova 2ドル$ i 3ドル$ zajedno ulaze u grad 6ドル,ドル zato što se ta grupa sastoji od dvoje ljudi, a grupa iz čvora 7ドル$ od samo jedne osobe, oni plaćaju dvostruku carinu tj. predstavnik grada 2ドル$ plaća carinu 6ドル$. Nakon toga zajedno predstavnici država 2ドル,ドル 3ドル,ドル 6ドル$ i 7ドル$ putuju u državu 1ドル$ te opet plaćaju dvostruku carinu kao najveća grupa, stoga predstavnik države 2ドル$ plaća 8ドル$. To čini ukupnu svotu 6ドル + 6 + 8 = 20$.

U petoj operaciji $lastans = 20$ stoga je $v = 16 ⊕ 20 = 5$. Predstavnik države 5ドル$ sam putuje u državu 1ドル,ドル zato što nije najveća grupa plaća jednostruku carinu tj. 4ドル$.