Description

在平面上给定一棵有根树，树根为 $1$，根的深度为 $0$。

对于深度为 $x$ 的节点，其 纵坐标 为 $n-x+1$。

对于一个节点的所有子节点，从左到右按照编号升序排列。每条边都是一条 连接两个点的线段。

每一个叶子节点都有一条 平行于 $y$ 轴且向 $y$ 轴负方向无限延伸的射线，根节点有一条 平行于 $y$ 轴且向 $y$ 轴正方向无限延伸的射线。

任意两条线段或射线只在树的节点处相交。

如果你不理解这个树是怎么画的，可以阅读样例 1 解释。

给定 $q$ 组 $u,v$，你现在要从点 $u$ 开始在平面上自由移动，但是你不能经过除 $u,v$ 以外的任何一个点，且每经过一条线段或射线就会产生 $1$ 的代价。

你的目标是移动到点 $v$，你需要求出移动过程产生的最小代价。

Input Format

由于直接输入会造成巨大的输入量，所以本题采用特殊的输入方式。

给定如下随机数生成器：

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;
}

第一行三个整数 $n,q,s$。

接下来一行 $n-1$ 个整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$。

接下来，如果 $s=-1$，则标准输入中的接下来 $q$ 行每行会有两个空格分隔的整数，代表询问的 $u'$ 和 $v'$；设上一次询问的答案为 $\text{lastans}$，你真正要处理的询问是 $u=u'\oplus \text{lastans}$ 和 $v=v'\oplus \text{lastans}$，其中 $\oplus$ 表示异或运算。如果这是第一次询问，则 $\text{lastans}=0$。

否则，你需要先调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $u$，再调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $v$。

Output Format

如果 $s=-1$，则输出 $q$ 行，每行是对应询问的答案。

如果 $s\geq 0$，则输出两个空格分隔的整数，分别表示所有答案的异或和和所有答案的和。

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.

样例 1 解释

第二次实际是询问 $u=6,v=3$，其他询问都满足 $u'=u,v'=v$。

• 可以看出，从 $4$ 到 $7$ 需要经过一条线；
• 从 $6$ 到 $3$ 不需要经过直线；
• 从 $5$ 到 $2$ 不需要经过直线；
• 从 $4$ 到 $8$ 需要经过一条线；
• 故答案分别为 $1,0,0,1$。

数据规模与约定

本题采用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据，$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$，且 $s=-1$ 时 $q\leq 5\times 10^5$。

对于 $99\%$ 的数据，保证 $s=-1$。

IO 量可能很大，请选择合适的读入输出方式。

说明

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

你问为什么 MCOI 里面混入了 AC6？
很简单，因为 ClCN 不玩 MC。