在 JOI 国有 $N$ 座城镇，编号为 $1$ 到 $N$。此外，JOI 国还有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。第 $j$ 条道路 ($1 \le j \le N-1$) 连接城镇 $U_j$ 和城镇 $V_j$，且双向通行。通过若干条道路，可以从任意城镇到达其他任意城镇。

每座城镇都有一家商店。在城镇 $i$ ($1 \le i \le N$) 的商店中，纪念品的售价为 $A_i$。

今年，JOI 国计划了 $M$ 次旅行。第 $k$ 次旅行 ($1 \le k \le M$) 从城镇 $S_k$ 出发，沿道路前往城镇 $T_k$，且不经过重复的城镇。注意，第 $k$ 次旅行会经过城镇 $S_k$ 和 $T_k$。保证 $S_k \neq T_k$。由于 JOI 国的结构，旅行经过的城镇序列是唯一确定的。

你计划参加其中一次旅行，并在旅行经过的城镇中恰好选择两座城镇各购买一件纪念品。此外，你希望恰好用完为购买纪念品准备的全部预算。因此，对于 $Q$ 个候选预算，你决定调查有多少种方法可以实现这一目标。

给定 JOI 国的道路、纪念品价格、旅行信息以及候选预算 $B_1, B_2, \dots, B_Q$，编写一个程序，计算选择一次旅行以及购买纪念品的城镇的方法数。更正式地说，对于每个 $q$ ($1 \le q \le Q$)，编写一个程序，计算满足以下所有条件的三元组整数 $(k, u, v)$ 的数量：

• $1 \le k \le M$。
• $1 \le u < v \le N$。
• 第 $k$ 次旅行经过城镇 $u$ 和 $v$。
• $A_u + A_v = B_q$。

输入格式

从标准输入读取以下数据：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $U_1 \ V_1$ $U_2 \ V_2$ $\vdots$ $U_{N-1} \ V_{N-1}$ $M$ $S_1 \ T_1$ $S_2 \ T_2$ $\vdots$ $S_M \ T_M$ $Q$ $B_1 \ B_2 \ \dots \ B_Q$

输出格式

输出 $Q$ 行到标准输出。第 $q$ 行 ($1 \le q \le Q$) 应包含选择一次旅行以及购买纪念品的城镇，使得预算 $B_q$ 被恰好用完的方法数。

数据范围

• $2 \le N \le 100\,000$。
• $1 \le A_i \le N$ ($1 \le i \le N$)。
• $1 \le U_j \le N$ ($1 \le j \le N-1$)。
• $1 \le V_j \le N$ ($1 \le j \le N-1$)。
• 可以通过若干条道路从任意城镇到达其他任意城镇。
• $1 \le M \le 200\,000$。
• $1 \le S_k \le N$ ($1 \le k \le M$)。
• $1 \le T_k \le N$ ($1 \le k \le M$)。
• $S_k \neq T_k$ ($1 \le k \le M$)。
• $1 \le Q \le 2\,000$。
• $1 \le B_1 < B_2 < \dots < B_Q \le 2N$。
• 所有输入值均为整数。

子任务

1. (3 分) $N \le 100, M \le 100, Q \le 100$。
2. (4 分) $N \le 5\,000, U_j = j$ ($1 \le j \le N-1$), $V_j = j+1$ ($1 \le j \le N-1$)。
3. (5 分) $N \le 5\,000$。
4. (6 分) $Q = 1, U_j = j$ ($1 \le j \le N-1$), $V_j = j+1$ ($1 \le j \le N-1$)。
5. (10 分) $Q = 1$。
6. (7 分) $M \le 1000, U_j = j$ ($1 \le j \le N-1$), $V_j = j+1$ ($1 \le j \le N-1$)。
7. (12 分) $M \le 1000$。
8. (10 分) $N \le 50\,000, M \le 50\,000, U_j = j$ ($1 \le j \le N-1$), $V_j = j+1$ ($1 \le j \le N-1$)。
9. (15 分) $N \le 50\,000, M \le 50\,000$。
10. (11 分) $U_j = j$ ($1 \le j \le N-1$), $V_j = j+1$ ($1 \le j \le N-1$)。
11. (17 分) 无附加限制。

样例

样例输入 1

8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
4
1 4
1 6
2 5
3 8
7
1 2 3 4 5 6 16

样例输出 1

0
0
4
2
4
1
0

样例输入 2

8
8 2 3 6 1 4 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1
1 8
5
2 4 5 10 15

样例输出 2

1
2
3
3
1