Description

A rooted tree is given on the plane, with root $1$, and the depth of the root is $0$.

For a node with depth $x$, its $y$-coordinate is $n-x+1$.

For all children of a node, they are ordered from left to right by increasing index. Each edge is a line segment connecting two points.

Each leaf node has a ray parallel to the $y$-axis and extending infinitely in the negative $y$ direction, and the root node has a ray parallel to the $y$-axis and extending infinitely in the positive $y$ direction.

Any two line segments or rays intersect only at the nodes of the tree.

If you do not understand how this tree is drawn, you can read the explanation of Sample 1.

Given $q$ pairs $(u, v)$, you now start from point $u$ and can move freely on the plane, but you are not allowed to pass through any point other than $u$ and $v$. Each time you pass through a line segment or a ray, it costs $1$.

Your goal is to move to point $v$. You need to find the minimum cost incurred during the movement.

Input Format

Direct input would cause an enormous input size, so this problem uses a special input method.

The following random number generator is given:

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

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

The next line contains $n-1$ integers describing the tree structure. The $i$-th number denotes the parent index $f_i$ of node $i+1$.

Then:

• If $s=-1$, then the next $q$ lines in standard input each contain two integers separated by a space, representing the query values $u'$ and $v'$. Let the answer to the previous query be $\text{lastans}$. The actual query you need to process is $u=u'\oplus \text{lastans}$ and $v=v'\oplus \text{lastans}$, where $\oplus$ denotes the XOR operation. If this is the first query, then $\text{lastans}=0$.
• Otherwise, you need to first compute $u=(\text{read}()\oplus \text{lastans})\bmod n+1$, and then compute $v=(\text{read}()\oplus \text{lastans})\bmod n+1$.

Output Format

If $s=-1$, output $q$ lines, each being the answer to the corresponding query.

If $s\geq 0$, output two integers separated by two spaces, representing the XOR of all answers and the sum of all answers, respectively.

9 4 -1
1 1 2 2 2 3 7 7
4 7
7 2
5 2
4 8

1
0
0
1

30 1 -1
1 2 3 4 5 6 7 7 9 9 11 11 12 13 13 14 17 18 19 20 21 19 23 22 22 25 25 28 29 
6 30

2

30 10000 20051130
1 2 3 4 5 6 7 7 9 9 11 11 12 13 13 14 17 18 19 20 21 19 23 22 22 25 25 28 29

2 6362

Hint

For the enhanced version, see P7434.

Sample 1 Explanation

In the second query, the actual query is $u=6, v=3$. All other queries satisfy $u'=u, v'=v$.

• It can be seen that going from $4$ to $7$ requires passing through one line.
• Going from $6$ to $3$ does not require passing through any line.
• Going from $5$ to $2$ does not require passing through any line.
• Going from $4$ to $8$ requires passing through one line.
• Therefore the answers are $1, 0, 0, 1$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (1 pts): $f_i=i-1$, $s=-1$.
• Subtask 2 (9 pts): $f_i=1$, $s=-1$.
• Subtask 3 (10 pts): $n, q\leq 2\times 10^3$, $s=-1$.
• Subtask 4 (20 pts): $f_i=\left\lfloor\dfrac{i}{2}\right\rfloor$, $s=-1$.
• Subtask 5 (59 pts): $s=-1$.
• Subtask 6 (1 pts): no special constraints.

For $100\%$ of the data: $1\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^6$, $1\leq u,v\leq n$, $1\leq f_i<i$, $-1\leq s\leq 10^9$, and when $s=-1$, $q\leq 5\times 10^5$.

For $99\%$ of the data, it is guaranteed that $s=-1$.

The IO size may be very large. Please choose appropriate input and output methods.

Notes

Minecraft OI Round 4 B
idea: ClCN solution: ClCN & _Guoyh_ check: _Guoyh_

You ask why AC6 is mixed into MCOI?
Very simple: because ClCN does not play MC.

Translated by ChatGPT 5