У Ксоні є кореневе дерево з n вершин з коренем у вершині 1, де на кожній вершині записано число. На i-й вершині записано число ai.
Нагадаємо, що деревом називається зв'язний граф без циклів. Кореневим деревом називається дерево, в якому вибрана одна вершина — корінь.
Предком вершини v в кореневому дереві називають усі вершини, які лежать на шляху від v до кореня крім самої вершини v. Піддеревом вершини v називають множину всіх вершин, для яких v є предком і саму вершину v.
XOR сумою множини S=(u1,u2,u3,…,uk) називається число u1⊕u2⊕u3⊕⋯⊕uk, де ⊕ — операція побітової виключної диз'юнкції, яка позначається як «xor» в мові Pascal і «^» в мовах C++/Java/Python.
Для множини чисел S розглянемо множину XOR-сум усіх можливих підмножин S. Назвемо цю множину F(S).
Друг Ксоні постійно питає в неї питання — "Якщо розглянути множину всіх чисел, записаних в піддереві вершини v (назвемо її Uv), то яке число в множині F(Uv) буде k-е за зростанням?". Тобто, якщо взяти всі числа з піддерева вершини v, розглянути всі XOR-суми їх підмножин, то яке число в отриманій множині буде на k-му місці за зростанням? Якщо такого числа немає (k>∣F(Uv)∣), то Ксоня відповідає числом −1. Зверніть увагу, що F(Uv) — множина, а не мультимножина. Тобто, якщо одне число зустрічається кілька разів, то його потрібно враховувати лише один раз.
Також, іноді друг Ксоні просить її змінити одне з чисел в дереві.
Перший рядок містить два цілі числа n,g (2≤n≤5⋅104, 0≤g≤7) — кількість вершин в дереві та номер групи.
Кожен з наступних n−1 рядків містить по два цілі числа xi,yi (1≤xi,yi≤n). Це означає, що в дереві проведено ребро між вершинами xi і yi. Гарантується, що граф — дерево.
Наступний рядок містить n цілих чисел a1,a2,…,an (0≤ai<220) — масив a початкових чисел на вершинах дерева.
Наступний рядок містить одне ціле число q (1≤q≤5⋅104) — кількість запитів.
Кожен з наступних q рядків описує один запит.
Запити на зміну числа в дереві мають вигляд 1 xi yi (1≤xi≤n, 0≤yi<220). Такий запит означає, що тепер на xi-й вершині записано число yi.
Запити іншого типу мають вигляд 2 vi ki (1≤vi≤n, 1≤ki≤109). Такий запит означає, що потрібно знайти ki-те за зростанням число у множині F(Uvi), де Uvi — множина чисел в піддереві вершини vi, а F(Uvi) — множина усіх можливих XOR-сум її підмножин. Якщо ki>∣F(Uvi)∣, виведіть −1.
На кожний запит другого типу виведіть відповідь в окремому рядку.
Пояснення першого прикладу. Числа біля вершин — ai.
В першому запиті розглядається піддерево вершини 2. Воно містить числа 1,2,3.
F([1,2,3])=[0,1,2,3].
В другому запиті розглядається все піддерево. F([1,2,3,4])=[0,1,2,3,4,5,6,7].
Після зміни одного числа дерево має такий вигляд.
Тепер в піддереві вершини 2 числа 1,2,4.
F([1,2,4])=[0,1,2,3,4,5,6,7].
(6 балів): q,n≤15.
(16 балів): q,n≤500.
(18 балів): q,n≤2000.
(7 балів): У всіх запитах другого типу vi=1.
(13 балів): Немає запитів на зміну числа.
(11 балів): Всі ai,yi — степені числа 2.
(29 балів): Без додаткових обмежень.