You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题仅作为长链剖分求树上 $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$。

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