Description

Given a rooted tree with $n$ nodes.

There are $q$ queries. In the $i$-th query, $x_i$ and $k_i$ are given. You need to find the $k_i$-th ancestor of node $x_i$, and denote the answer as $ans_i$. In particular, $ans_0 = 0$.

The queries in this problem are generated within the program.

A random seed $s$ and a random function $\operatorname{get}(x)$ are given:

#define ui unsigned int
ui s;

inline ui get(ui x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x; 
}

You need to generate the queries in order.

Let $d_i$ be the depth of node $i$, where the root has depth $1$.

For the $i$-th query, $x_i = ((\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod n) + 1$, and $k_i = (\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod d_{x_i}$.

Input Format

The first line contains three integers $n, q, s$.

The second line contains $n$ integers $f_{1\dots n}$, where $f_i$ is the parent of $i$. In particular, if $f_i = 0$, then $i$ is the root.

Output Format

Output one integer per line, representing $\operatorname{xor}_{i=1}^q i \times ans_i$.

6 3 7
5 5 2 2 0 3

1

Hint

[Sample Explanation]

$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$.
Therefore, the output is $1$.

For $20\%$ of the testdata, $n, q \le 10^3$.

For $50\%$ of the testdata, $n, q \le 10^5$.

For $100\%$ of the testdata, $2 \le n \le 5 \times 10^5$, $1 \le q \le 5 \times 10^6$, $1 \le s < 2^{32}$.

Translated by ChatGPT 5