给你一棵拥有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。每个顶点 $i$ 都被赋予了一种颜色 $c_i$。

你需要处理 $Q$ 个查询。在每个查询中，给定四个整数 $u_1, v_1, u_2, v_2$。

对于每个查询，求出满足以下条件的最大整数 $K$ ($0 \le K \le N$)：

• 对于每个 $j = 1, 2, \dots, K$，从 $u_1$ 到 $v_1$ 的路径上颜色为 $j$ 的顶点数等于从 $u_2$ 到 $v_2$ 的路径上颜色为 $j$ 的顶点数。

输入格式

输入按以下格式给出：

$$ \begin{array}{l} N \\ a_1 \ b_1 \\ a_2 \ b_2 \\ \vdots \\ a_{N-1} \ b_{N-1} \\ c_1 \ c_2 \ \dots \ c_N \\ Q \\ \text{Query}_1 \\ \text{Query}_2 \\ \vdots \\ \text{Query}_Q \end{array} $$

每个 $\text{Query}$ 按以下格式给出：

$$ u_1 \ v_1 \ u_2 \ v_2 $$

数据范围

• $1 \le N \le 100\,000$
• $1 \le a_i, b_i \le N$ ($1 \le i \le N - 1$)
• $1 \le c_i \le N$ ($1 \le i \le N$)
• $1 \le Q \le 100\,000$
• $1 \le u_1, v_1, u_2, v_2 \le N$ ($1 \le i \le Q$)
• 给定的图是一棵树。
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。在第 $i$ 行（$1 \le i \le Q$）输出第 $i$ 个查询的答案。

样例

样例输入 1

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

样例输出 1

0
6
6
0