给定一棵有 $n$ 个顶点的有根树，顶点编号为 $0, \dots, n-1$，根节点编号为 $0$。对于每个 $i \in \{0, \dots, n-1\}$，顶点 $i$ 被赋予一个整数 $a_i$。令 $f_v$ 为从顶点 $v$ 到根节点的简单路径上所有顶点 $a$ 值的按位与（以下记作 $\&$）结果。（注意：从顶点 $x$ 到顶点 $y$ 的简单路径包含 $x$ 和 $y$ 本身。）令树的“能量”（power）为以下值：

$$\sum_{0 \le u, v < n} f_u \cdot f_v$$

令树的“超能量”（superpower）为以下值（注意范围的区别）：

$$\sum_{0 \le u < v < n} f_u \cdot f_v$$

若顶点 $v$ 在顶点 $u$ 到根节点的简单路径上，则称顶点 $u$ 属于顶点 $v$ 的子树。注意，顶点 $x$ 的子树包含 $x$ 本身。

你需要处理 $q$ 次更新。每次更新由两个整数 $v$ 和 $x$ 描述，要求将顶点 $v$ 子树中每个顶点 $u$ 的 $a_u$ 更新为 $a_u \& x$。每次更新后，你需要输出当前树的能量和超能量。

由于输出值可能很大，请将结果对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n-1$ 个整数 $p_1, p_2, \dots, p_{n-1}$，它们决定了树的结构。对于每个 $i \in \{1, \dots, n-1\}$，$p_i$ 是顶点 $i$ 的父节点编号，且满足 $0 \le p_i < i$。

第三行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$，这些是赋予各顶点的初始值。

接下来的 $q$ 行，每行包含两个整数 $v$ ($0 \le v < n$) 和 $x$，表示一次更新。

输出格式

输出 $q+1$ 行。每行包含两个由空格分隔的整数。第一行输出初始树的能量和超能量（对 $10^9 + 7$ 取模）。在剩余的 $q$ 行中，第 $i$ 行（$i \in \{1, \dots, q\}$）输出第 $i$ 次更新后树的能量和超能量（对 $10^9 + 7$ 取模）。

数据范围

• $1 \le n, q \le 10^6$
• $0 \le a_i < 2^{60}$，对于每个 $i \in \{0, \dots, n-1\}$
• $0 \le x < 2^{60}$，对于每次更新 $(v, x)$

子任务

1. (4 分) $n = 3$
2. (7 分) $n, q \le 700$
3. (13 分) $n, q \le 5000$
4. (6 分) $n \le 10^5$，$p_i = i - 1$（对于每个 $i \in \{1, \dots, n-1\}$），且 $a_i, x < 2^{20}$
5. (7 分) $p_i = i - 1$（对于每个 $i \in \{1, \dots, n-1\}$）
6. (12 分) $a_i, x < 2^{20}$（对于每个 $i \in \{0, \dots, n-1\}$ 及每次更新）
7. (14 分) $n \le 10^5$
8. (11 分) $n \le 5 \cdot 10^5$
9. (26 分) 无附加限制

样例

样例输入 1

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

样例输出 1

196 61
169 50
81 14
25 6

说明 1

初始时，$f_0 = 7, f_1 = 7\&3 = 3, f_2 = 7\&4 = 4$。 能量为 $196$，超能量为 $61$。

样例输入 2

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

样例输出 2

256 84
144 36
16 4

样例输入 3

7 3
0 0 1 1 2 2
7 6 5 7 3 4 2
4 4
3 3
2 1

样例输出 3

900 367
784 311
576 223
256 83