【模板】树上 K 级祖先

题目背景

本题仅作为长链剖分求树上 $k$ 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。

题目描述

给定一棵 $n$ 个点的有根树。

有 $q$ 次询问，第 $i$ 次询问给定 $x_i, k_i$，要求点 $x_i$ 的 $k_i$ 级祖先，答案为 $ans_i$。特别地，$ans_0 = 0$。

本题中的询问将在程序内生成。

给定一个随机种子 $s$ 和一个随机函数 $\operatorname{get}(x)$：

#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$。

输入样例 #1

6 3 7
5 5 2 2 0 3

输出样例 #1

1

输入样例 #2

120 120 1646367862
0 1 1 3 4 4 1 4 4 7 8 9 8 8 9 1 12 3 9 1 14 9 1 12 4 2 16 10 12 24 16 30 21 33 9 34 13 34 37 22 39 14 30 18 1 9 24 39 18 7 31 8 3 32 30 4 16 24 5 51 43 32 12 34 33 45 26 33 61 52 56 62 39 24 53 62 56 14 76 69 15 79 72 42 65 6 37 28 8 4 67 25 73 18 70 54 9 37 76 26 17 71 37 31 86 88 83 41 61 101 66 49 92 87 99 20 63 95 9 77

输出样例 #2

12276

输入样例 #3

140 140 1584865053
0 1 2 1 4 5 2 4 1 6 8 2 12 8 2 1 5 10 16 2 13 5 21 2 18 23 2 27 18 18 28 25 21 30 9 3 6 29 3 20 14 26 27 31 44 4 35 9 33 45 1 42 44 7 36 15 16 23 36 47 51 12 57 1 49 62 26 15 51 7 68 40 8 58 62 31 3 38 72 5 78 76 48 17 76 63 75 66 25 26 49 33 76 2 54 36 87 95 39 31 70 40 42 18 63 84 4 16 90 3 58 77 52 17 69 25 80 54 73 32 107 40 118 56 28 22 119 6 21 62 81 81 96 113 36 130 119 46 24 46

输出样例 #3

5730

数据范围

对于 $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}$。