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.
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$$$.
Minden típusú lekérdezésnél külön sorba írja ki a választ.
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
3 1 2 0 7 4
Az első példa magyarázata. Számok a csúcsok közelében — $$$a_i$$$.
$$$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]$$$.