题目背景

这是一个作战部署命令。

我们已经从国家安全局获得了有关敌方重型指挥巡洋舰的部分机密情报。

敌方巡航机的正式名称已被确认为 P-1112 Aigaion。

空中舰队中包含一种 Kottos 中型巡航机负责电子支援，还有一种 Gyges 中型巡航机负责近程防空。

Aigaion，作为指挥机，负责一切与巡航导弹相关的事务。

在获得这些情报之后，我们可以草拟一个摧毁 Aigaion 的计划。

仔细听好了。

Aigaion 只能在机体前部接受空中加油。

多架加油机必须同时处在 Aigaion 前方才能进行加油作业。

当加油机在 Aigaion 前部进行加油时，Aigaion 的雷达探测能力会暂时削弱。

这里就是关键点了。

Aigaion 在进行加油时，其雷达基本完全无法探测在其前方飞行的物体。

如果你们能维持在一个固定航线并在一个特定高度上飞行，你们就能在不被敌军发现的情况下，从空中接近 Aigaion。

所以我们解决掉这只怪物的最佳时机就是它进行空中加油的时候。

Aigaion 的预定航线图也包含在这份情报中。

简报结束后，我们将在机库再次检查航线图。

快去准备吧。

…………

Garuda 队，交战！

$$_{{\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\ - $$

题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

给定如下随机数生成器：

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$ 表示异或运算。

输出格式

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

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

提示

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$。

---

「魂归大海……」

「你可以休息了……」

「安息吧。」