【模板】树上 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 << 13; x ^= x >> 17; x ^= x << 5; return s = x; } ``` 你需要按顺序依次生成询问。 设 $d_i$ 为点 $i$ 的深度，其中根的深度为 $1$。 对于第 $i$ 次询问，$x_i = ((\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod n) + 1$，$k_i = (\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod d_{x_i}$。

第一行三个整数 $n, q, s$。 第二行 $n$ 个整数 $f_{1\dots n}$，其中 $f_i$ 表示 $i$ 的父亲。特别地，若 $f_i = 0$，则 $i$ 为根。

一行一个整数，表示 $\operatorname{xor}_{i=1}^q i \times ans_i$。

6 3 7
5 5 2 2 0 3

1

【样例说明】 $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}$。