Description

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

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

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

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

每个线段或射线带一个权值。

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

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

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

你的目标是移动到点 $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$ 行，每行两个整数，分别表示这个节点在树上的父亲 $f_i$ 和其到父亲的边的权值 $w_i$。

接下来一个整数 $w_1$，表示节点 $1$ 向上的射线的权值。

接下来一行若干个空格分隔的整数 $d_u$，按照 叶子节点编号从小到大（注意不是在树上从左到右） 的顺序给出所有叶子节点向下的射线的权值。

接下来，对于每一组询问，设上一次询问的答案为 $\text{lastans}$，如果这是第一次询问，则 $\text{lastans}=0$。你需要先调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $u$，再调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $v$。其中 $\oplus$ 表示异或运算。

Output Format

输出两个空格分隔的整数，分别表示所有答案的异或和和所有答案的和。

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

2 6362

Hint

idea：Sol1，solution：dengyaotriangle & Sol1 & Guoyh，code：Sol1，data：Sol1

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^6$，$1\leq f_i<i$，$1\leq w_i,w_1,d_{u}\leq 2\times 10^3$，$0\leq s\leq10^9$。

「魂归大海……」

「你可以休息了……」

「安息吧。」