Xonia és a fa
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A Xonia-nak van egy $$$n$$$ csúcsú gyökérfája, amelynek gyökér az $$$1$$$,. csúcsban van, ahol minden csúcsra egy szám van írva. Az $$$a_i$$$ számot az $$$i$$$–edik csúcsra írjuk.

Emlékezzünk vissza, hogy a fa egy hurok nélküli összekapcsolt gráf. A gyökérfa olyan fa, amelyben egy csúcs van kiválasztva — egy gyökér.

A gyökérfában a $$$v$$$ csúcs ősének nevezzük az összes olyan csúcsot, amely a $$$v$$$ és a gyökér közötti útvonalon fekszik, kivéve magát a $$$v$$$ csúcsot. A $$$v$$$ csúcs részfája azon csúcsok halmaza, amelyeknek $$$v$$$ az őse és maga a $$$v$$$ csúcs.

A $$$S = (u_1, u_2, u_3, \dots, u_k)$$$ XOR összegét $$$u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k$$$ számnak nevezzük, ahol $$$\oplus$$$ — bitenkénti kizárólagos műveleti diszjunkció, «xor» ábrázolják, Pascalban «^», C++/Java/Python pedig «^».

A $$$S$$$ számok halmazához vegyük figyelembe a $$$S$$$ összes lehetséges részhalmazának XOR-összegeit. Nevezzük ezt a halmazt $$$F(S)$$$-nek.

Xonia barátja folyamatosan felteszi neki a kérdést — "Ha figyelembe vesszük a $$$v$$$ csúcs részfájába írt összes szám halmazát (nevezzük $$$U_v$$$), akkor melyik szám a $$$F(U_v)$$$ halmazban $$$k$$$-e lesz a növekedés? Vagyis ha az összes számot a $$$v$$$ csúcs részfájából vesszük, figyelembe vesszük részhalmazaik összes XOR-összegét, akkor a kapott halmazban melyik szám lesz a $$$k$$$ -edik helyen növekvő sorrendben? Ha nincs ilyen szám ($$$k > |F(U_v)|$$$), akkor a Xonia a $$$-1$$$ számmal felel. Vegye figyelembe, hogy a $$$F(U_v)$$$ — egy halmaz, nem pedig egy multihalmaz. Vagyis ha egy szám többször előfordul, akkor azt csak egyszer kell figyelembe venni.

Emellett néha Xonia barátja megkéri, hogy változtassa meg a fán lévő egyik számot.

Input

Az első sor két egész számot tartalmaz: $$$n, g$$$ ($$$2 \leq n \leq 5 \cdot 10^4$$$, $$$0 \leq g \leq 7$$$) — a fa csúcsainak számát és a csoport számát.

A következő $$$n - 1$$$ sorok mindegyike két egész számot tartalmaz: $$$x_i, y_i$$$ ($$$ 1 \leq x_i, y_i \leq n$$$). Ez azt jelenti, hogy a $$$x_i$$$ és $$$y_i$$$ csúcsok közötti él megrajzolódik a fában. Garantáltan a gráf — fa.

A következő sor $$$n$$$ egész számot tartalmaz: $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$) — $$$a$$$ kezdeti számokból álló tömb a fa csúcsainál.

A következő sor egy egész számot tartalmaz: $$$q$$$ ($$$1 \leq q \leq 5 \cdot 10^4$$$) — a lekérdezések száma.

A következő $$$q$$$ sorok mindegyike egy-egy lekérdezést ír le.

A fában szereplő szám módosítására vonatkozó kérések így néznek ki $$$1 \ x_i \ y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$ 0 \leq y_i < 2^{20}$$$). Ez a lekérdezés azt jelenti, hogy a $$$y_i$$$ szám most a $$$x_i$$$ csúcsra van írva. Más típusú lekérdezések, a következőképp néznek ki $$$2 \ v_i \ k_i$$$ ($$$1 \leq v_i \leq n$$$, $$$1 \leq k_i \leq 10^9$$$). Ez a lekérdezés azt jelenti, hogy meg kell találni a $$$k_i$$$ növekvő számot a $$$F(U_{v_i})$$$, halmazban, ahol $$$U_{v_i}$$$ — a számok halmaza a $$$v_i$$$ csúcs részfájában, és $$$F(U_{v_i})$$$ — részhalmazainak összes lehetséges XOR összegének halmaza. Ha $$$k_i > |F(U_{v_i})|$$$, írja ki $$$-1$$$.

Output

Minden típusú lekérdezésnél külön sorba írja ki a választ.

Scoring

  1. ($$$6$$$ pont): $$$q, n \leq 15$$$.
  2. ($$$16$$$ pont): $$$q, n \leq 500$$$.
  3. ($$$18$$$ pont): $$$q, n \leq 2000$$$.
  4. ($$$7$$$ pont): A második típusú összes lekérdezésben $$$v_i = 1$$$.
  5. ($$$13$$$ pont): Nincsenek számmódosítási kérelmek.
  6. ($$$11$$$ pont): Minden $$$a_i, y_i$$$ 2 hatványa.
  7. ($$$29$$$ pont): Nincsenek további korlátozások.

Example

Input
5 0
1 2
1 5
2 3
2 4
4 2 3 1 2
7
2 2 4
2 1 2
2 2 3
1 3 4
2 5 1
2 2 8
2 1 5
Output
3
1
2
0
7
4

Note

Az első példa magyarázata. Számok a csúcsok közelében — $$$a_i$$$.

Az első lekérdezés egy $$$2$$$ vertex részfát vizsgál. Ez tartalmazza a $$$1, 2, 3$$$ számokat

$$$F([1,2,3]) = [0, 1, 2, 3]$$$.

A második lekérdezés a teljes részfát veszi figyelembe. $$$F([1, 2, 3, 4]) = [0,1,2,3,4,5,6,7]$$$.

Egy szám megváltoztatása után a fa így néz ki.

Most a $$$2$$$ csúcs részfájában a $$$1, 2, 4$$$ szám.

$$$F([1,2,4]) = [0,1,2,3,4,5,6,7]$$$.