说明

Ryan 有一棵 $N$ 个节点的有根树，每个节点上写有一个数字 $0$ 或 $1$。

Ryan 的朋友也有一棵有根树，每个节点上写有一个数字 $0$ 或 $1$。设这棵树的节点数为 $M$。

Ryan 想将这 $N + M$ 个节点排成水平的一行。这里，对于每个节点，不允许它的任何祖先出现在它的右侧。注意，Ryan 的树中的节点与他朋友的树中的节点之间没有任何约束。

排列好节点后，令 $X$ 为从左到右读取节点上数字得到的序列。Ryan 希望最小化 $X$ 的逆序数。请求出 $X$ 可能的最小逆序数。

由于 Ryan 有 $Q$ 个朋友，请对每个朋友分别解决上述问题。

朋友树上节点所写的数字是以加密形式给出的。具体细节请参见输入格式部分的说明。

输入格式

输入包含一个测试用例，格式如下。

$$\begin{aligned} & N \\ & P_2 \ P_3 \ \ldots \ P_N \\ & V_1 \ V_2 \ \ldots \ V_N \\ & Q \\ & M_1 \\ & P_{1,2} \ P_{1,3} \ \ldots \ P_{1,M_1} \\ & U_{1,1} \ U_{1,2} \ \ldots \ U_{1,M_1} \\ & M_2 \\ & P_{2,2} \ P_{2,3} \ \ldots \ P_{2,M_2} \\ & U_{2,1} \ U_{2,2} \ \ldots \ U_{2,M_2} \\ & \vdots \\ & M_Q \\ & P_{Q,2} \ P_{Q,3} \ \ldots \ P_{Q,M_Q} \\ & U_{Q,1} \ U_{Q,2} \ \ldots \ U_{Q,M_Q} \end{aligned}$$

第一行包含一个整数 $N$（$1 \leq N \leq 200\,000$），表示 Ryan 的树的节点数。

第二行包含 $N - 1$ 个整数。每个 $P_i$（$2 \leq i \leq N$，$1 \leq P_i < i$）表示节点 $i$ 的父节点是节点 $P_i$。注意节点 $1$ 是树的根，$P_1$ 未给出。

第三行包含 $N$ 个整数。每个 $V_i$（$1 \leq i \leq N$，$0 \leq V_i \leq 1$）表示写在节点 $i$ 上的数字。

第四行包含一个整数 $Q$（$1 \leq Q \leq 100\,000$），表示 Ryan 的朋友数量。

对于每个朋友 $k$（$1 \leq k \leq Q$），他们的树的信息按以下格式给出：

• 第一行包含一个整数 $M_k$（$1 \leq M_k$），表示第 $k$ 个朋友的树的节点数。
• 第二行包含 $M_k - 1$ 个整数。每个 $P_{k,i}$（$2 \leq i \leq M_k$，$1 \leq P_{k,i} < i$）表示节点 $i$ 的父节点是节点 $P_{k,i}$。注意节点 $1$ 是树的根，$P_{k,1}$ 未给出。
• 第三行包含 $M_k$ 个整数。每个 $U_{k,i}$（$1 \leq i \leq M_k$，$0 \leq U_{k,i} \leq 1$）表示第 $k$ 个朋友的树上节点 $i$ 的加密数字。

此外，所有 $M_k$（$1 \leq k \leq Q$）的总和不超过 $200\,000$。

解密朋友树上节点的数字

令 $X_0 = 0$，对于每个朋友 $k$（$1 \leq k \leq Q$），令 $X_k$ 表示第 $k$ 个朋友的答案。第 $k$ 个朋友的树上节点 $i$ 所写的实际值 $V_{k,i}$（$1 \leq k \leq Q$，$1 \leq i \leq M_k$，$0 \leq V_{k,i} \leq 1$）由以下公式确定：

$$V_{k,i} = (\text{powmod}(X_{k-1}, i, 998244353) + U_{k,i}) \mod 2.$$

这里，$\text{powmod}(a, b, m)$ 表示 $(a^b \mod m)$。

输出格式

输出 $Q$ 行。第 $i$ 行应包含一个整数，表示 Ryan 与他的第 $i$ 个朋友对应的最小可能逆序数。

6
1 1 2 3 3
0 1 1 0 0 0
4
4
1 2 2
1 0 1 0
6
1 1 2 3 3
1 1 0 0 1 0
1

0
15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0

9
7
4
42

提示

解密后的样例如下所示：

6
1 1 2 3 3
0 1 1 0 0 0
4
4
1 2 2
1 0 1 0
6
1 1 2 3 3
0 0 1 1 0 1
1

1
15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 1

翻译由 DeepSeek V3.2 完成