Xonia és a fa#11071
A Xonia-nak van egy csúcsú gyökérfája, amelynek gyökér az ,. csúcsban van, ahol minden csúcsra egy szám van írva. Az a_i számot az –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 csúcs ősének nevezzük az összes olyan csúcsot, amely a és a gyökér közötti útvonalon fekszik, kivéve magát a csúcsot. A csúcs részfája azon csúcsok halmaza, amelyeknek az őse és maga a 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 — bitenkénti kizárólagos műveleti diszjunkció, «xor» ábrázolják, Pascalban «^», C++/Java/Python pedig «^».
A számok halmazához vegyük figyelembe a összes lehetséges részhalmazának XOR-összegeit. Nevezzük ezt a halmazt -nek.
Xonia barátja folyamatosan felteszi neki a kérdést — "Ha figyelembe vesszük a 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 -e lesz a növekedés? Vagyis ha az összes számot a 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 -edik helyen növekvő sorrendben? Ha nincs ilyen szám (k > |F(U_v)|), akkor a Xonia a 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: (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 egész számot tartalmaz: a_1, a_2, \dots, a_n (0 \leq a_i < 2^{20}) — kezdeti számokból álló tömb a fa csúcsainál.
A következő sor egy egész számot tartalmaz: (1 \leq q \leq 5 \cdot 10^4) — a lekérdezések száma.
A következő 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 .
Minden típusú lekérdezésnél külön sorba írja ki a választ.
1. példa
Az első példa magyarázata. Számok a csúcsok közelében — a_i.
Az első lekérdezés egy vertex részfát vizsgál. Ez tartalmazza a 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 csúcs részfájában a szám.
F([1,2,4]) = [0,1,2,3,4,5,6,7].
( pont): q, n \leq 15.
( pont): q, n \leq 500.
( pont): q, n \leq 2000.
( pont): A második típusú összes lekérdezésben v_i = 1.
( pont): Nincsenek számmódosítási kérelmek.
( pont): Minden a_i, y_i 2 hatványa.
( pont): Nincsenek további korlátozások.