Problem Background

This is a combat deployment order.

We have obtained some classified intelligence about the enemy's heavy command cruiser from the National Security Agency.

The formal name of the enemy's cruiser has been confirmed as P-1112 Aigaion.

The aerial fleet includes a Kottos medium cruiser responsible for electronic support and a Gyges medium cruiser responsible for short-range air defense.

Aigaion, as the command vessel, oversees all matters related to cruise missiles.

After obtaining this intelligence, we can draft a plan to destroy Aigaion.

Listen carefully.

Aigaion can only receive aerial refueling at the front of the aircraft.

Multiple tankers must be positioned in front of Aigaion simultaneously to conduct refueling operations.

When refueling is underway at the front of Aigaion, its radar detection capability is temporarily weakened.

This is the key point.

During refueling, Aigaion's radar is essentially unable to detect objects flying in front of it.

If you can maintain a fixed course and fly at a specific altitude, you can approach Aigaion undetected from the air.

Therefore, the best opportunity to take down this monster is when it is refueling.

The scheduled flight path of Aigaion is also included in this intelligence.

After the briefing, we will review the flight path in the hangar.

Go prepare.

…………

Garuda Squad, engage!

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$

Problem Description

Given a rooted tree in a plane, with the root being node $1$ and its depth being $0$.

For a node at depth $x$, its vertical coordinate is $n-x+1$.

For all child nodes of a node, they are ordered from left to right in ascending order by their numbers. Each edge is a 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 segments or rays intersect only at the nodes of the tree.

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

Given $q$ pairs of $u, v$, you start at point $u$ and move freely in the plane, but you cannot pass through any point other than $u, v$, and each segment or ray you pass through incurs a cost of $1$.

Your goal is to move to point $v$, and you need to find the minimum cost of the movement process.

Input Format

Due to the large input size, this problem uses a special input method.

Given the following random number generator:

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 represents the parent node number $f_i$ of node $i+1$.

If $s=-1$, the next $q$ lines each contain two space-separated integers representing the queries $u'$ and $v'$; let the answer to the previous query be $\text{lastans}$, the actual queries to process are $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 call $(\text{read}()\oplus \text{lastans})\bmod n+1$ once to get the query $u$, and then call $(\text{read}()\oplus \text{lastans})\bmod n+1$ again to get the query $v$.

Output Format

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

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
0
0
1

Input Sample #2

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

Output Sample #2

2

Input Sample #3

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

Output Sample #3

2 6362

Notes/Hints

For the enhanced version, see P7434.

Sample 1 Explanation

The second actual query is $u=6, v=3$, while other queries satisfy $u'=u, v'=v$.

• It can be seen that moving from $4$ to $7$ requires passing through one segment;
• Moving from $6$ to $3$ does not require passing through any segments;
• Moving from $5$ to $2$ does not require passing through any segments;
• Moving from $4$ to $8$ requires passing through one segment;
• Hence, the answers are $1, 0, 0, 1$.

Data Size and Constraints

This problem uses bundled testing.

• 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, $s=-1$.

The IO volume may be large, please choose an appropriate input and output method.

Notes

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

You ask why AC6 is mixed in with MCOI?
Simple, because ClCN doesn't play MC.

见题面 Input 部分

见题面 Output 部分