На день народження Askhat отримав від NurlashKO у подарунок кореневе дерево з $n$ вершинами, пронумерованими від $1$ до $n$. Дерево — це зв'язний неорієнтований граф без циклів. Коренем дерева є вершина з номером $1$. Вершина $v$ є предком вершини $u$, якщо $v$ лежить на найкоротшому шляху від $u$ до кореня. Найнижчий спільний предок послідовності вершин $(x_1,x_2,\ldots,x_k)$ — це найдальша від кореня вершина, яка є предком $x_i$ для всіх $1\le i\le k$; позначимо її $\operatorname{lca}(x_1,x_2,\ldots,x_k)$.

Окрім подарунка, NurlashKO підготував для Askhat завдання. Спершу він повідомив послідовність довжини $m$ — $(a_1,a_2,\ldots,a_m)$, кожне число якої є вершиною дерева. Вершини в послідовності можуть повторюватися. Потім він почав ставити $q$ запитів, кожен з яких має один із двох типів:

• $1\ pos\ v$ — NurlashKO просить Askhat змінити значення в позиції $pos$ на $v$, тобто $a_{pos}=v$.
• $2\ l\ r\ v$ — NurlashKO просить Askhat знайти пару $(x,y)$ таку, що $l\le x\le y\le r$ і $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$, або повідомити, що такої пари немає.

Askhat витратив багато часу на дослідження подарунка і тепер просить вашої допомоги.

Вхідні дані

Перший рядок вхідних даних містить три додатні цілі числа $n,m,q$ — розмір дерева, довжину послідовності та кількість запитів. Наступні $n-1$ рядків містять ребра дерева $(u_i,v_i)$ ($u_i\ne v_i$). Наступний рядок містить $m$ цілих чисел $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$) — послідовність, яку NurlashKO подарував Askhat. Кожен із наступних $q$ рядків описує запит. Якщо перше число запиту дорівнює $1$, за ним ідуть два числа $pos$ і $v$ ($1\le pos\le m$, $1\le v\le n$) — це запит першого типу. Якщо перше число запиту дорівнює $2$, за ним ідуть три числа $l,r,v$ ($1\le l\le r\le m$, $1\le v\le n$) — це запит другого типу. Гарантується, що серед $q$ запитів є принаймні один запит другого типу.

Вихідні дані

Для кожного запиту другого типу виведіть два числа $x$ і $y$ — відповідь на нього. Якщо розв'язку немає, виведіть -1 -1 (без лапок). Якщо розв'язків кілька, виведіть будь-який із них.

Підзадачі

Задача складається з чотирьох підзадач; у кожній із них тести задовольняють обмеження умови:

1. $1\le n,m,q\le 100$. 12 балів.
2. $1\le n,m,q\le 500$. 18 балів.
3. $1\le n,m,q\le 2000$. 26 балів.
4. $1\le n,m,q\le 2\cdot 10^5$. 44 бали.

Приклад

Вхідні дані 1

5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

Вихідні дані 1

1 3
3 3
-1 -1

Пояснення

• Послідовність: $[4,5,2,3]$.
• Підвідрізок $=[4,5,2]$, $v=1$. $\operatorname{lca}(4,5,2)=1$, відповідь: $(1,3)$.
• Запит на зміну, нова послідовність: $[4,5,5,3]$.
• Підвідрізок $=[5,3]$, $v=5$. $\operatorname{lca}(5)=5$, відповідь: $(3,3)$.
• Підвідрізок $=[4,5,5]$, $v=1$. $\operatorname{lca}(4)=4$, $\operatorname{lca}(5)=5$, $\operatorname{lca}(4,5)=3$, $\operatorname{lca}(5,5)=5$, $\operatorname{lca}(4,5,5)=3$. Розв'язку немає.