Description

树是一种无向连通图，满足图上不存在环。

当我们指定树的某一个点为根，此时除了根节点外，每个点在树上有且仅有一个父亲。

现在给定一棵以 $1$ 为根的树，有多次询问，每次询问某一个点 $x$ 的第 $d$ 个父亲。一个点的第 $0$ 个父亲就是自己，第 $1$ 个父亲就是其树上的父亲（如果存在的话），第 $2$ 个父亲是其父亲的父亲（如果存在的话）。也就是说你要求出 $x$ 往根节点走 $d$ 条边以后到达的点的编号，$d$ 可能是 $0$。

如果所求的父亲不存在，请回答 $0$。

你必须在每次询问之后在线地给出答案。如果你不了解什么是在线，你只需要继续阅读以下内容。

输入格式和输出格式

接下来所有描述的运算均在32位无符号整数下运行。

这道题中需要输入、输出的信息可能会很多，因此你需要采取以下方式来输入、输出：

输入第一行是两个非负整数 $seed1，seed2$，是两个参数。

输入第二行是三个正整数 $n，m，k$。其中 $n$ 是树的点数，$m$ 是询问组数，$k$ 是一个参数。

接下来的 $n-1$ 行，每行是两个正整数 $u，v$，表示树上的一条边。

现在有几个参数 $tseed$，$ans$ 和 $mul$。询问开始前 $tseed=0，ans=0，mul=1$。

每次询问的时候你要获得 $x$ 和 $d$，表示从 $x$ 这个点往上跳 $d$ 步的父亲是哪一个点。获得方法如下：

第一步，tseed 变为 (tseed * seed1 + seed2) ^ ans。x 为此时的 tseed % N + 1。

第二步，tseed 变为 (tseed * seed1 + seed2) ^ ans。d 为此时的 tseed % k。

其中 $seed1，seed2$ 和 $k$ 是输入的参数，% 表示取模运算，^ 表示二进制运算中的按位异或运算。在C++中，你可以直接用 a^b 来得到 a 和 b 按位异或运算的结果。

根据获得的 $x$ 和 $d$，你得到了这组询问的答案，假设叫做 $t$。那么这次询问之后：

第一步，ans 变为 ans + mul * t + seed2;

第二步，mul 变为 mul * seed2。

其中 $seed2$ 是输入的参数。

最后，你要输出的只有一个整数，就是 $ans$。

以上所有描述的运算均在32位无符号整数下运行。

如果你清楚以上内容的含义，可以忽略接下来的这一段提示。

本题提供了C++参考代码，你可以借助参考代码来完成你的代码。

你只需要实现这份代码里的两个函数：

void init(int n, int m, int k_lim, int u[], int v[]);

在这个函数里你可以对输入数据中的树进行初始化。其中 $n,m,k$ 如题所述，$u[]$ 和 $v[]$ 两个数组存储了输入的边，并且下标从 $0$ 开始。也就是真实输入数据的第 $i$ 条边的两个顶点存储在数组 $u[i-1]$ 和 $v[i-1]$ 的位置上。

int jump(int x, int d);

在这个函数里你要回答从 $x$ 这个点往上跳 $d$ 步的父亲是哪一个点。如果不存在，返回 $0$。

请注意，不论你是否有使用参考代码，评测时的时间、内存均以你提交的代码为准。参考代码部分的运行时间和内存，计算进最终评测的时间和内存。

Output Format

Sample

样例一输入

233 666
2 5 2
1 2

样例一输出

3233534703

样例一解释

询问次数	$x$	$d$	本组询问的答案	询问后的ans的值
第一次询问	$1$	$0$	$1$	$667$
第二次询问	$2$		$2$	$2665$
第三次询问				$890443$
第四次询问				$591707701$
第五次询问				$3233534703$

样例二输入输出

请见下发的选手目录。

Hint

请注意本题中所有描述的运算均在32位无符号整数下运行。

对于所有数据，保证给定的树合法，且 $0 \le seed1, seed2 < 2^{32}$。

本题一共有 $10$ 个测试点，每个测试点 $10$ 分。

各个测试点的其余约束如下：

| 测试点编号 | $n=$ | $m=$ | $k=$ | 特殊性质 |

| ---------- | -------- | ---------- | ----- | -------- |

| $1$ | $2$ | $10$ | 1 | 无 |

| $2$ | $2$ | $10$ | 2 | 无 |

| $3$ | $1000$ | $1000$ | 20 | 无 |

| $4$ | $1000$ | $1000$ | 100 | 无 |

| $5$ | $1000$ | $1000$ | 500 | 无 |

| $6$ | $100000$ | $100000$ | 50000 | 性质1 |

| $7$ | $100000$ | $100000$ | 2 | 性质2 |

| $8$ | $100000$ | $100000$ | 20000 | 无 |

| $9$ | $100000$ | $100000$ | 16 | 无 |

| $10$ | $100000$ | $10000000$ | 83 | 无 |

性质1：给定的树中，第 $i$ 条边连接 $i$ 号点和 $i+1$ 号点。

性质2：给定的树中，第 $i$ 条边连接 $1$ 号点和 $i+1$ 号点。