Askhat 在生日时收到了一棵有 $n$ 个顶点的有根树作为礼物，顶点编号从 $1$ 到 $n$。树是一个没有环的连通无向图。树的根是编号为 $1$ 的顶点。如果顶点 $v$ 位于从顶点 $u$ 到根的简单路径上，则称 $v$ 是 $u$ 的祖先。顶点序列 $(x_1, x_2, \dots, x_k)$ 的最近公共祖先（$lca(x_1, x_2, \dots, x_k)$）是距离根最远且同时是所有 $1 \le i \le k$ 的 $x_i$ 的祖先的顶点。

除了礼物外，NurlashKO 还为 Askhat 准备了一个任务。首先，他给出了一个长度为 $m$ 的序列 $(a_1, a_2, \dots, 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$ 且 $lca(a_x, a_{x+1}, \dots, a_y) = v$。或者指出不存在这样的对。

Askhat 花了很多时间研究这份礼物，现在他需要你的帮助。

输入格式

第一行包含三个正整数 $n, m$ 和 $q$ — 树的大小、序列的长度和询问次数。接下来的 $n-1$ 行包含树的边 $(u_i, v_i)$ ($u_i \neq v_i$)。下一行包含 $m$ 个整数 $a_1, a_2, \dots, 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$。$lca(4, 5, 2) = 1$，答案：$(1, 3)$。
• 修改询问，新序列：$[4, 5, 5, 3]$
• 子段 $= [5, 3], v = 5$。$lca(5) = 5$，答案：$(3, 3)$。
• 子段 $= [4, 5, 5], v = 1$。$lca(4) = 4, lca(5) = 5, lca(4, 5) = 3, lca(5, 5) = 5, lca(4, 5, 5) = 3$。无解。