P5903 [Template] $K$-th Ancestor on a Tree

**This problem is only for judging solutions that use long chain decomposition to find the $k$-th ancestor on a tree, and it does not guarantee that other methods with incorrect complexity will be rejected.**

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: ```cpp #define ui unsigned int ui s; inline ui get(ui x) { x ^= x > 17; x ^= x

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 one integer per line, representing $\operatorname{xor}_{i=1}^q i \times ans_i$.

[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