Kth Ancestor Query on a Rooted Tree

Given a rooted tree with (n) nodes numbered from 1 to (n) (the root is node 1) and (q) queries, your task is to answer queries for the (k)-th ancestor of a given node. In each query, given two numbers (x_i) and (k_i), you need to output (ans_i), the (k_i)-th ancestor of node (x_i). Note that by definition, the 0-th ancestor of any node is the node itself. Furthermore, we set (ans_0 = 0).

The queries are generated internally using the following process. A global unsigned integer variable (s) is given as the random seed. Define the random function (\operatorname{get}(x)) as follows:

[ \begin{aligned} &x \mathrel{\oplus}= x \ll 13,\ &x \mathrel{\oplus}= x \gg 17,\ &x \mathrel{\oplus}= x \ll 5,\ & s = x, \quad \text{and return } x. \end{aligned} ]

Let (d_i) denote the depth of node (i) (with (d_1 = 1) for the root). For the (i)-th query ((1 \le i \le q)), the parameters are generated as:

[ \begin{aligned} x_i &= \bigl((\operatorname{get}(s) \oplus ans_{i-1}) \bmod n\bigr) + 1,\ k_i &= (\operatorname{get}(s) \oplus ans_{i-1}) \bmod d_{x_i}. \end{aligned} ]

Your task is to process all (q) queries in order and output the answer for each query in a new line. It is guaranteed that the query parameters are generated so that the (k_i)-th ancestor of (x_i) always exists.

Input Format:

• The first line contains three integers \(n\), \(q\), and \(s\) (the number of nodes, the number of queries, and the seed for randomness).
• The second line contains \(n-1\) integers, where the \(i\)-th integer (for \(i = 2, 3, \ldots, n\)) is the parent of node \(i\).

Output Format:

• Output \(q\) lines, each containing a single integer representing the answer for the corresponding query.

Note: Use (k=0) to denote the query for the 0-th ancestor, which by definition is the node itself.

inputFormat

The input consists of two lines:

• The first line contains three space-separated integers \(n\), \(q\) and \(s\), where \(n\) is the number of nodes, \(q\) is the number of queries, and \(s\) is the random seed.
• The second line contains \(n-1\) space-separated integers \(p_2, p_3, \ldots, p_n\), where \(p_i\) denotes the parent of node \(i\) (\(i \ge 2\)).

outputFormat

Output \(q\) lines. The \(i\)-th line should contain the integer \(ans_i\), the answer for the \(i\)-th query.

sample

3 1 0
1 1

1

</p>