题目背景

链的部分分官方数据有误。这里已经修改，如仍有误请反馈。

题目描述

K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多 $c$ 颗宝石，其收集宝石的顺序为：$P_1, P_2, \ldots , P_c$。更具体 地，收集器需要先放入第 $P_1$ 种宝石，然后才能再放入第 $P_2$ 种宝石，之后再能放入第 $P_3$ 种宝石，以此类推。其中 $P_1, P_2, \ldots , P_c$ 互不相等。

K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。

现在 K 神给了你 $q$ 次询问，每次给出起点 $s_i$ 与终点 $t_i$，他想知道如果从 $s_i$ 号城市出发，沿最短路线走到 $t_i$ 号城 市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）

输入格式

第一行，包含三个正整数 $n, m, c$，分别表示城市数，宝石种类数，收集器的容量。 第二行，包含 $c$ 个正整数 $P_i$。数据保证 $1 \le P_i \le m$ 且这些数互不相等。 第三行，包含 $n$ 个正整数 $w_i$，表示每个城市集市上出售的宝石种类。 接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示一条连接 $u_i$ 和 $v_i$ 号城市的道路。 接下来一行，包含一个正整数 $q$，表示询问次数。 接下来 $q$ 行，每行两个正整数 $s_i, t_i$，表示该次询问的起点与终点。

输出格式

按输入顺序输出 $q$ 行，每行一个整数，表示询问的答案。

输入输出样例 #1

7 3 3
2 3 1
2 1 3 3 2 1 3
1 2
2 3
1 4
4 5
4 6
6 7
5
3 5
1 3
7 3
5 7
7 5

2
2
2
3
1

输入输出样例 #2

见附件中的 gem/gem2.in

见附件中的 gem/gem2.ans

输入输出样例 #3

见附件中的 gem/gem3.in

见附件中的 gem/gem3.ans

说明/提示

【数据范围】

对于所有测试数据：$1 \le n, q \le 2 \times {10}^5$，$1 \le c \le m \le 5 \times {10}^4$，$1 \le w_i \le m$。

每个测试点的具体限制见下表：

\begin{array}{|c|c|c|} \hline \textbf{测试点编号} & n, q \le & \textbf{特殊限制} \\ \hline 1 \sim 2 & 10 & \textbf{无} \\ \hline 3 \sim 5 & 1000 & \textbf{无} \\ \hline 6 \sim 10 & 2 \times {10}^5 & m \le 300 \\ \hline 11 \sim 14 & 2 \times {10}^5 & u_i = i\textbf{，}v_i = i + 1 \\ \hline 15 \sim 20 & 2 \times {10}^5 & \textbf{无} \\ \hline \end{array}