U676773 污染

随着许多工厂的建立，W 小镇的河流污染问题变得愈发严重。为了保护环境，科学家决定在河流附近建立检测站来检测污染程度。 W 小镇的河流可以视作一棵 $n$ 个节点的有根树，其中编号为 $1$ 的根节点对应河流的源头，而第 $i(i > 1)$ 号节点的直接上游是编号为 $f_i(1 \le f_i < i)$ 的节点。初始所有节点的污染度均为 $0$. 科学家组成了 $m$ 个环境保护小组，每个小组在河流的一些节点上放置了污染监测器。为了保证环保工作的有序进行，有根树的每个节点上都会恰好放置一个小组的监测器，$i$ 号点的监测器属于 $a_i$ 号小组。 有 $q$ 个工厂依次建成。第 $i$ 个工厂建在编号为 $u_i$ 的节点上，工厂建成后会对 $u_i$ 及其子树中的所有节点造成不可逆的污染，使这些节点的污染度**永久**增加 $x_i$. 对于一个小组，若其所有监视器所在节点的污染度之和**严格小于**小组设置的阈值，则说明该小组负责的河流区域环境处于正常状态，否则处于恶劣状态。第 $i$ 个小组对应的阈值为 $s_i$. 在每个工厂建成后，你需要回答有哪些小组负责的区域环境为恶劣状态。 环境保护刻不容缓，题目中的部分测点**强制在线**。对于这些测点，你需要在每次工厂建成后立刻进行回答。

第一行输入一个整数 $C$,表示强制在线系数。 第二行输入三个整数 $n,m,q$，分别表示节点数量，小组数量与工厂数量。 第三行输入 $n-1$ 个整数，第 $i$ 个数 $f_{i+1}$ 表示第 $i+1$ 号节点的直接上游。 第四行输入 $n$ 个整数，第 $i$ 个数 $a_i$ 表示第 $i$ 号节点上的监视器归属的小组编号。 第五行输入 $m$ 个整数，第 $i$ 个数 $s_i$ 表示 $i$ 号小组设置的阈值。 接下来 $q$ 行，每行有两个加密后的整数 $U_i,X_i$ 。你需要通过如下方式进行解密： $u_i = U_i \oplus (C \times lastans)$ $x_i = X_i \oplus (C \times lastans)$ 其中 $lastans$ 为上一次查询的答案对 $998244353$ 取模后的结果，对于第一次查询，$lastans = 0$. $u_i,x_i$ 表示第 $i$ 个工厂在 $u_i$ 号节点建成，会对 $u_i$ 子树中所有节点(包括 $u_i$)造成 $x_i$ 点污染。

输出 $q$ 行，每行输出一个整数，表示有哪些小组的环境处于恶劣状态。 环境是否进入恶劣状态可以用一个长度为 $m$ 的二进制数表示，其中**从低到高**第 $i$ 位为 1 则表示第 $i$ 个小组负责的环境处于恶劣状态中。 为了减小输出量，你只需要输出这个整数转化为十进制后对 $998244353$ 取模的结果即可。

【样例解释1】 - 第一座工厂建成后，三个小组污染度总和分别为: $0,1,2$. - 第二座工厂建成后，三个小组污染度总和分别为: $1,3,5$. 此时一号小组开始进入恶劣状态。 - 第三座工厂建成后，三个小组污染度总和分别为: $2,5,8$. - 第四座工厂建成后，三个小组污染度总和分别为: $2,7,12$. 此时三号小组开始进入恶劣状态。 - 第五座工厂建成后，三个小组污染度总和分别为: $2,10,12$. 此时二号小组开始进入恶劣状态。 【样例解释2】 样例 2 解密后与样例 1 完全一致。 【数据范围】 $1\le n,m,q\le 3\cdot10^5$ ,$1 \le a_i \le m$ ,$0\le s_i\le 2 \times 10^9$,$C \in \{0,1 \}$. 保证解密后 $1 \le u_i \le n,0 \le x_i \le 2 \times 10^9$. | 测试点编号 | $n \le$ | $m \le$ | $q \le$ | 特殊性质 | | :--------: | :-------------: | :-------------: | :-------------: | :------: | | $1$~$2$ | $3000$ | $3000$ | $3000$ | 无 | | $3$~$7$ | $3 \times 10^5$ | $3 \times 10^5$ | $3 \times 10^5$ | A | | $8$~$10$ | $3 \times 10^5$ | $3 \times 10^5$ | $3 \times 10^5$ | BC | | $11$~$14$ | $3 \times 10^5$ | $3 \times 10^5$ | $3 \times 10^5$ | C | | $15$~$20$ | $3 \times 10^5$ | $3 \times 10^5$ | $3 \times 10^5$ | 无 | - 特殊性质 A 为: $C=0$. - 特殊性质 B 为: $n=m$ 且 $\forall 1 \le i \le n , a_i = i$. - 特殊性质 C 为: 每个小组的监视器数量不超过 $2$.