Description

树是一种无向连通图，满足图上不存在环。
当我们指定树的某一个点为根，此时除了根节点外，每个点在树上有且仅有一个父亲。
现在给定一棵以 1为根的树，有多次询问，每次询问某一个点 x 的第 d 个父亲。一个点的第 0 个父亲就是自己，第 1 个父亲就是其树上的父亲（如果存在的话），第 2 个父亲是其父亲的父亲（如果存在的话）。也就是说你要求出 x 往根节点走d条边以后到达的点的编号，d可能是 0。
如果所求的父亲不存在，请回答 0。
你必须在每次询问之后在线地给出答案。如果你不了解什么是在线，你只需要继续阅读以下内容。

Format

【输入格式和输出格式】
接下来所有描述的运算均在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开始。也就是真实输入数据的第 iii 条边的两个顶点存储在数组 u[i−1]和 v[i−1] 的位置上。
int jump(int x, int d);
在这个函数里你要回答从x 这个点往上跳 d步的父亲是哪一个点。如果不存在，返回 0。

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

Sample 1

Input

233 666
2 5 2
1 2

Output

3233534703

Limitation

2s, 512MiB for each test case.