P5903 【模板】树上 K 级祖先
题目背景
**本题仅作为长链剖分求树上 $k$ 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。**
题目描述
给定一棵 $n$ 个点的有根树。
有 $q$ 次询问，第 $i$ 次询问给定 $x_i, k_i$，要求点 $x_i$ 的 $k_i$ 级祖先，答案为 $ans_i$。特别地，$ans_0 = 0$。
本题中的询问将在程序内生成。
给定一个随机种子 $s$ 和一个随机函数 $\operatorname{get}(x)$：
```cpp
#define ui unsigned int
ui s;
inline ui get(ui x) {
x ^= x > 17;
x ^= x
输入格式
无
输出格式
无
说明/提示
【样例说明】
$x_1 = 4$，$k_1 = 1$，$ans_1 = 2$；
$x_2 = 6$，$k_2 = 3$，$ans_2 = 5$；
$x_3 = 3$，$k_3 = 0$，$ans_3 = 3$；
故输出 $1$。
---
对于 $20\%$ 的数据，$n,q \le 10^3$。
对于 $50\%$ 的数据，$n,q \le 10^5$。
对于 $100\%$ 的数据，$2 \le n \le 5 \times 10^5$，$1 \le q \le 5 \times 10^6$，$1 \le s < 2^{32}$。