Background

BackUP，没背景。

Description

给定一颗点带权无根树，给出 $q$ 次询问，每次给出 $(r,x)$，求这棵树在以 $r$ 为根的情况下子树 $x$ 的 $\operatorname{mex}$。

提示：一个集合的 $\operatorname{mex}$ 指这个集合中最小的没有出现过的自然数。

本题部分测试点强制在线。

Format

Input

第一行三个整数 $id,n,q$ 代表本测试点编号、树的结点个数以及询问个数。

接下来 $n-1$ 行每行两个正整数 $(u,v)$ 表示一条边。

接下来一行 $n$ 个自然数，第 $i$ 个自然数表示结点 $i$ 的权值，这个值为在 $[0,n]$ 之间的自然数。

接下来 $q$ 行每行两个正整数 $r,u$ 表示一组询问。

对于“强制在线”的测试点，真实的 $r,u$ 需要异或上一次询问的结果 $lastans$ 才能得到，这些测试点初始时 $lastans=id$。

Output

输出一行一个整数，设第 $i$ 次询问的答案为 $ans_i$，则你需要输出 $\operatorname{xor}_{i=1}^{n}(i\times ans_i)$，其中 $\operatorname{xor}$ 表示按位异或运算。

请注意答案的数据范围。

Samples

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

25

本样例不满足强制在线。

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

25

本样例为上一样例的强制在线版本。

Limitation

数据范围：

设结点 $i$ 的点权为 $a_i$，对所有测试点，满足 $\forall i \in [1,n],a_i\in[0,n],2\le n\le 5\times 10^5,1\times q \le 5\times 10^5$，所有询问满足 $1\le r,x\le n$。

测试点编号	$n=$	$q=$	强制在线	特殊性质
$1$	$30$	$10$	否	无
$2$	$5\times 10^5$	$50$
$3$		$5\times 10^5$		BE
$4$				A
$5$				B
$6$				DE
$7$				D
$8$				E
$9-12$				无
$13$	$5000$		是
$14$	$5\times 10^5$			AE
$15$				C
$16$				D
$17$				B
$18-19$				E
$20-25$				无

特殊性质A：所有点的点权 $\in[0,1]$。

特殊性质B：所有点的点权构成一个 $[0,n-1]$ 的排列。

特殊性质C：整棵树是一条链。

特殊性质D：整棵树是一个菊花。

特殊性质E：所有询问满足 $r=\min\{n,id\}$。