English Problem Statement

这是一道交互题，且仅支持 C++ 语言

在之前的比赛中，“闪电跳蚤”与“量子跳蚤”以戏剧性的平局收场，双方选手同时冲线，连高速摄像机都无法分辨胜负。为了彻底决出最强战队，跳蚤国王决定举办一场史无前例的“百里马拉松”——这场比赛将覆盖整个跳蚤国的城市网络！

跳蚤国有 $n$ 个城市，编号为 $1\sim n$，其中 $1$ 号城市为首都跳蚤利亚，并且这 $n$ 个城市的连边情况构成了一棵树。

现在跳蚤国打算举办一场“百里马拉松”，具体来说，一场马拉松可以用两个参数 $(x,d)$ 来表示，其中 $d$ 表示马拉松比赛的规模，$x$ 表示马拉松比赛的起点所在城市，马拉松比赛的终点为首都。

对于一场马拉松 $(x,d)$，会导致城市 $x$ 到首都最短路径上的所有城市都会产生噪音，一个城市如果距离某一个有噪音的城市（可以是自身）的距离 $\le d$，那么该城市的所有居民就会前来围观。

每个城市都居住了一些跳蚤，伏特想知道有多少跳蚤会前来围观。然而这些数据属于国家机密，所以伏特并不能获得。

具体来说，每个城市的跳蚤数会被加密然后存放在一个 info 类型中，并且 info 类型封装了加法。

现在马拉松的计划还没完全定下来。你需要通过至多 $M_1$ 次 info 类型的加法运算进行预处理，然后对于每个计划，用至多 $M_2$ 次 info 类型的加法运算计算出该计划会前来围观的跳蚤数。

实现细节

选手需确保提交的程序包含头文件 match.h，可以在程序开头加入以下代码：

#include "match.h"

头文件包含以下内容：

1. 定义了信息对应的数据类型 info。保证一个 info 消耗 $8$ 个字节内存。
2. 定义了 $0$ 加密后得到的 info 类型的量 empty_info。
3. 封装了 info 类型的加法。具体的，你可以调用如下运算符：

   info operator + (info a,info b);

4. 定义并实现了判定一个 info 解密后是否为 $0$ 的函数 isempty(info a)，这个函数返回真当且仅当 a 解密后为 $0$。

你不需要，也不应该实现主函数，你需要实现如下几个函数：

void init(int n,vector<int> fa,vector<info> a,int task_id)

$n$ 表示树的节点数，$fa$ 数组的长度为 $n-1$，依次对应 $2\sim n$ 这些节点的父亲，$a$ 数组的长度为 $n$，依次对应城市 $1\sim n$ 的跳蚤数加密后的结果，task_id 表示对应的 Subtask 编号。

保证对于一个测试点，init 只会被调用恰好一次。

info query(int x,int d)

表示查询对于一场马拉松，城市中前来围观的跳蚤数量之和。参数的意义详见题目描述。

注意，未初始化的 info 变量初值不是 empty_info。

头文件中实现了 main 函数，也就是说，你可以直接在调用了 match.h 头文件后直接编译运行你的程序。另外，你的最终程序不应访问标准输入输出，但允许访问 stderr。

最终测试时所用的交互库实现与该实现有不同，因此选手的解法不应依赖交互库的具体实现，同时也不应该依赖 match.h 中 info 类型的具体实现。

下发的 match.h 与评测时的 match.h 的差异：

下发 grader 中未初始化的 info 变量初值为 empty_info，但实际 grader 中并不是。

下发 grader 中 info 类型的大小为 4 字节，实际 grader 中 info 类型的大小为 8 字节。

实际测试中，两个 info 相加如果其中有至少一个是 empty_info，那么这次加法运算不计入次数限制内。

输入格式

第一行六个整数 $n,Q,id,seed,M_1,M_2$，分别表示树的节点数、询问数量，子任务编号（样例则为 $0$），随机种子（用于评测的加密），和两个限制参数。使用下发的 match.h 时需保证 $seed=0$。

第二行 $n-1$ 个整数，分别表示 $f{a}_2,f{a}_3,\cdots ,f{a}_n$，分别表示 $2\sim n$ 的父亲节点，调用时需保证 $f{a}_i<i$。

第三行 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，表示城市 $1\sim n$ 的跳蚤数，本地调用时需保证 $a_i\in [0,{10}^4]$。

接下来 $Q$ 行，每行两个整数 $x,d$，描述一次询问。

输出格式

如果预处理次数超过了 $M_1$，那么程序会输出 wrong 1 并退出。

下发交互库一共会输出 $Q+1$ 行，其中第 $1\sim Q$ 行每行两个整数，分别表示一次查询的答案以及加法操作调用次数。如果此时加法操作调用次数超过了 $M_2$ 那么程序会输出 wrong 2 并退出。第 $Q+1$ 行输出两个数，分别表示预处理操作中加法的调用次数以及单个询问中加法调用次数的最大值。

注意评测使用的交互库并不会输出第 $Q+1$ 行。

样例零

input

5 4 0 0 100000 10
1 1 2 2
1 10 100 1000 10000
1 1
3 0
2 1
4 0

output

111
101
11111
1011

注意这里并没有给出第 $Q+1$ 行的结果。

样例一~五

见下发文件。

数据范围

对于所有数据，保证 $1\le n\le 3\times {10}^5,1\le Q\le min(3\times {10}^5,\lfloor {10}^6/M_2\rfloor )$，保证 $1\le x\le n,0\le d\le n$。

特殊性质 A：保证节点 $i$ 的父亲在 $1\sim i-1$ 中随机。

特殊性质 B：保证 $d\ge 100$。

时间限制：$\mathtt{\text{5s}}$

空间限制：$\mathtt{\text{1GB}}$

关于 hack

如果你想 Hack 别人，请按照输入格式造数据，并保证 $seed=0$。