马里博尔刚刚迎来了外星人！他们与你分享了他们的技术和历史。

共有 $N + 1$ 个行星，编号从 $0$ 到 $N$，其中地球的编号为 $N$。每个行星都有一个唯一的人口数量（第 $i$ 个行星的人口为 $P[i]$，其中 $i \in \{0, \dots, N\}$）。这些行星通过 $N$ 个双向传送门连接，使得你可以仅通过这些传送门在任意两个行星之间旅行。传送门 $i$（$i \in \{0, \dots, N - 1\}$）连接行星 $U[i]$ 和 $V[i]$。两个行星之间的距离是它们之间旅行所需的最少传送门数量。

你从地球出发，想要进行一次远足，访问其他 $K$ 个行星——$A[0], A[1], \dots, A[K - 1]$。这些被称为起源行星。你还知道每个起源行星和地球都只连接了一个传送门。你的远足是一条最短路线，它从地球出发，访问所有起源行星以及沿途的所有行星。令 $S$ 为所有被访问行星的集合。

现在外星人决定通过询问你 $Q$ 个两种类型的问题，来测试地球是否有资格加入他们的超级文明。

• 类型 1：集合 $S$ 的大小是多少？
• 类型 2：他们选择集合 $S$ 中的一个行星 $x$、一个距离 $d$ 和一个数字 $r$。他们问你，在距离 $x$ 为 $d$ 的所有行星中，按人口数量排序第 $r$ 小的行星是哪一个？（例如，如果 $r = 1$，这就是人口最少的行星。该行星可以属于集合 $S$，也可以不属于。）

类型 1 的询问恰好有一次。

输入格式

第 1 行：$N, K, Q$。 第 2 行：$P[0], \dots, P[N]$。 第 3 行：$A[0], \dots, A[K - 1]$。 接下来的 $N$ 行中，第 $i$ 行（$i \in \{0, \dots, N - 1\}$）包含：$U[i]$ 和 $V[i]$。

接下来的 $Q$ 行满足以下格式之一： 1（类型 1 的询问） 2 x d r（类型 2 的询问）

输出格式

对于每个询问，在一行中打印答案。要么是远足期间访问的行星数量，要么是距离 $x$ 为 $d$ 的行星中按人口排序第 $r$ 小的行星编号。

数据范围

• $1 \le N \le 100\,000$；$1 \le K \le 10$；$1 \le Q \le 100\,000$。
• 对于 $0 \le i \le N$，满足 $1 \le P[i] \le 10^9$。所有 $P[i]$ 均唯一。
• 对于 $0 \le i \le K - 1$，满足 $0 \le A[i] \le N - 1$。
• 对于 $0 \le i \le N - 1$，满足 $0 \le U[i], V[i] \le N$。
• $K$ 个起源行星和地球都恰好连接了一个传送门。
• 对于每个询问，给出一个值 $1 \le t \le 2$。当 $t = 2$ 时，给出额外的值 $x, d$ 和 $r$。满足 $x \in S$，$d \ge 1$ 且 $r \ge 1$。
• 保证在距离行星 $x$ 为 $d$ 的地方至少有 $r$ 个行星。

子任务

1. (3 分) $Q = 1$。
2. (14 分) $N \le 2000, Q \le 2000$。
3. (21 分) $K = 1$。
4. (12 分) $N \le 10\,000$。
5. (13 分) $Q \le 10\,000$。
6. (37 分) 无附加限制。

样例

样例输入 1

5 1 5
8 7 9 4 16 12
1
0 4
3 1
2 4
5 4
4 3
1
2 4 2 1
2 3 2 1
2 4 1 3
2 5 2 3

样例输出 1

4
1
0
2
2

说明

有一个起源行星，我们在远足期间访问了行星 $S = \{1, 3, 4, 5\}$。类型 2 的询问如下：

• $x = 4, d = 2, r = 1$
  • 在距离行星 4 为 2 的地方，只有行星 1。
• $x = 3, d = 2, r = 1$
  • 在距离行星 3 为 2 的地方，有行星 0、2 和 5。其中，行星 0 的人口最少。
• $x = 4, d = 1, r = 3$
  • 在距离行星 4 为 1 的地方，有行星 0、2、3 和 5，按人口排序为 3, 0, 2, 5。其中第三个是行星 2。
• $x = 5, d = 2, r = 3$
  • 在距离行星 5 为 2 的地方，有行星 0、2 和 3，按人口排序为 3, 0, 2。其中第三个是行星 2。

样例输入 2

10 2 11
1 2 3 4 5 6 7 8 9 10 11
9 3
5 8
2 7
3 4
6 8
0 1
2 9
5 2
4 5
7 10
1 2
1
2 5 1 2
2 5 2 2
2 5 2 3
2 5 2 4
2 9 3 2
2 9 3 3
2 9 4 1
2 2 1 3
2 2 2 4
2 2 3 1

样例输出 2

7
4
3
6
7
4
8
3
7
10
3