У Ксоні є кореневе дерево з $n$ вершин з коренем у вершині $1$, де на кожній вершині записано число. На $i$-й вершині записано число $a_i$. Нагадаємо, що деревом називається зв'язний граф без циклів. Кореневим деревом називається дерево, в якому вибрана одна вершина --- корінь. Предком вершини $v$ в кореневому дереві називають усі вершини, які лежать на шляху від $v$ до кореня крім самої вершини $v$. Піддеревом вершини $v$ називають множину всіх вершин, для яких $v$ є предком і саму вершину $v$. XOR сумою множини $S = (u_1, u_2, u_3, \dots, u_k)$ називається число $u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k$, де $\oplus$ --- операція побітової виключної диз'юнкції, яка позначається як <<xor>> в мові Pascal і <<\^>> в мовах C++/Java/Python. Для множини чисел $S$ розглянемо множину XOR-сум усіх можливих підмножин $S$. Назвемо цю множину $F(S)$. Друг Ксоні постійно питає в неї питання --- "Якщо розглянути множину всіх чисел, записаних в піддереві вершини $v$ (назвемо її $U_v$), то яке число в множині $F(U_v)$ буде $k$-е за зростанням?". Тобто, якщо взяти всі числа з піддерева вершини $v$, розглянути всі XOR-суми їх підмножин, то яке число в отриманій множині буде на $k$-му місці за зростанням? Якщо такого числа немає ($k > |F(U_v)|$), то Ксоня відповідає числом $-1$. Зверніть увагу, що $F(U_v)$ --- множина, а не мультимножина. Тобто, якщо одне число зустрічається кілька разів, то його потрібно враховувати лише один раз. Також, іноді друг Ксоні просить її змінити одне з чисел в дереві. \InputFile Перший рядок містить два цілі числа $n, g$ ($2 \leq n \leq 5 \cdot 10^4$, $0 \leq g \leq 7$) --- кількість вершин в дереві та номер групи. Кожен з наступних $n - 1$ рядків містить по два цілі числа $x_i, y_i$ ($ 1 \leq x_i, y_i \leq n$). Це означає, що в дереві проведено ребро між вершинами $x_i$ і $y_i$. Гарантується, що граф --- дерево. Наступний рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($0 \leq a_i < 2^{20}$) --- масив $a$ початкових чисел на вершинах дерева. Наступний рядок містить одне ціле число $q$ ($1 \leq q \leq 5 \cdot 10^4$) --- кількість запитів. Кожен з наступних $q$ рядків описує один запит. Запити на зміну числа в дереві мають вигляд $1 \ x_i \ y_i$ ($1 \leq x_i \leq n$, $ 0 \leq y_i < 2^{20}$). Такий запит означає, що тепер на $x_i$-й вершині записано число $y_i$. Запити іншого типу мають вигляд $2 \ v_i \ k_i$ ($1 \leq v_i \leq n$, $1 \leq k_i \leq 10^9$). Такий запит означає, що потрібно знайти $k_i$-те за зростанням число у множині $F(U_{v_i})$, де $U_{v_i}$ --- множина чисел в піддереві вершини $v_i$, а $F(U_{v_i})$ --- множина усіх можливих XOR-сум її підмножин. Якщо $k_i > |F(U_{v_i})|$, виведіть $-1$. \OutputFile На кожний запит другого типу виведіть відповідь в окремому рядку. \Note Пояснення першого прикладу. Числа біля вершин --- $a_i$. \begin{center} \includegraphics[scale = 0.5]{https://static.eolymp.com/content/1d/1ddd28c4ecb94ba9b24bfa8357afd60e.png} \end{center} В першому запиті розглядається піддерево вершини $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]$. Після зміни одного числа дерево має такий вигляд. \begin{center} \includegraphics[scale = 0.5]{https://static.eolymp.com/content/aa/aab9478611534a5ea34157c24924a8a6.png} \end{center} Тепер в піддереві вершини $2$ числа $1, 2, 4$. $F([1,2,4]) = [0,1,2,3,4,5,6,7]$. \Scoring \begin{enumerate} \item ($6$ балів): $q, n \leq 15$. \item ($16$ балів): $q, n \leq 500$. \item ($18$ балів): $q, n \leq 2000$. \item ($7$ балів): У всіх запитах другого типу $v_i = 1$. \item ($13$ балів): Немає запитів на зміну числа. \item ($11$ балів): Всі $a_i, y_i$ --- степені числа 2. \item ($29$ балів): Без додаткових обмежень. \end{enumerate}