给定一棵以节点 $1$ 为根的有根树。对于树中的任意节点 $i$ ($1 < i \le n$)，都有一条连接节点 $i$ 和 $p_i$ ($1 \le p_i < i$) 的边，其边权为 $t_i$。

Iris 不知道 $t_i$ 的具体数值，但她知道 $\sum_{i=2}^n t_i = w$，且每个 $t_i$ 都是一个非负整数。

树的节点以一种特殊的方式进行编号：每个子树中的节点编号都是连续的整数。换句话说，树的节点是按照深度优先搜索（DFS）的顺序进行编号的。

上图中的树满足该条件。例如，在节点 2 的子树中，节点编号为 2, 3, 4, 5，它们是连续的整数。

上图中的树不满足该条件，因为在节点 2 的子树中，节点编号 2 和 4 不是连续的整数。

我们定义 $\operatorname{dist}(u, v)$ 为树中节点 $u$ 和 $v$ 之间简单路径的长度。

接下来，将发生 $n - 1$ 个事件：

• Iris 得到了整数 $x$ 和 $y$，表示 $t_x = y$。

在每个事件之后，Iris 想要独立地求出对于每个 $i$ ($1 \le i \le n$)，$\operatorname{dist}(i, i \bmod n + 1)$ 的最大可能值。她只需要知道这 $n$ 个值的和。请帮助 Iris 快速求出答案。

注意，在计算 $\operatorname{dist}(i, i \bmod n + 1)$ 和 $\operatorname{dist}(j, j \bmod n + 1)$（其中 $i \ne j$）的最大可能值时，未知的边权可以不同。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $w$ ($2 \le n \le 2 \cdot 10^5$, $0 \le w \le 10^{12}$) —— 树的节点数和边权之和。

每个测试用例的第二行包含 $n - 1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) —— 树的边的描述。

接下来 $n - 1$ 行表示事件。每行包含两个整数 $x$ 和 $y$ ($2 \le x \le n$, $0 \le y \le w$)，表示 $t_x = y$。

保证在所有事件中，所有的 $x$ 互不相同。同时保证所有 $y$ 的和等于 $w$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含 $n-1$ 个整数，分别表示每个事件发生后的答案。

样例

输入样例 1

4
2 1000000000000
1
2 1000000000000
4 9
1 1 1
2 2
4 4
3 3
6 100
1 2 3 2 1
6 17
3 32
2 4
4 26
5 21
10 511
1 2 2 4 2 1 1 8 8
3 2
6 16
10 256
9 128
2 1
5 8
8 64
4 4
7 32

输出样例 1

2000000000000
25 18 18
449 302 247 200 200
4585 4473 2681 1567 1454 1322 1094 1022 1022

说明

在第一个测试用例中，$\operatorname{dist}(1, 2) = \operatorname{dist}(2, 1) = t_2 = w = 10^{12}$，因此 $\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 2 \cdot 10^{12}$。

在第二个测试用例中，在 Iris 知道所有的 $t_x$ 之后，树的形态如下图所示：

$\operatorname{dist}(1, 2) = t_2$，$\operatorname{dist}(2, 3) = t_2 + t_3$，$\operatorname{dist}(3, 4) = t_3 + t_4$，$\operatorname{dist}(4, 1) = t_4$。在第一个事件之后，她发现 $t_2 = 2$，因此 $\operatorname{dist}(1, 2) = 2$。与此同时：

• 如果 $t_3 = 7, t_4 = 0$，则 $\operatorname{dist}(2, 3)$ 取得最大值。此时 $\operatorname{dist}(2, 3) = 9$。
• 如果 $t_3 = 0, t_4 = 7$，则 $\operatorname{dist}(3, 4)$ 和 $\operatorname{dist}(4, 1)$ 取得最大值。此时 $\operatorname{dist}(3, 4) = \operatorname{dist}(4, 1) = 7$。

因此，答案为 $2 + 9 + 7 + 7 = 25$。

在第二个事件之后，她发现 $t_4 = 4$，此时 $t_3 = w - t_2 - t_4 = 3$。$\operatorname{dist}(1, 2) = 2$，$\operatorname{dist}(2, 3) = 2 + 3 = 5$，$\operatorname{dist}(3, 4) = 3 + 4 = 7$，$\operatorname{dist}(4, 1) = 4$。因此，答案为 $2 + 5 + 7 + 4 = 18$。