去年圣诞节，你有一棵可爱的圣诞树。这棵树有 $n$ 个节点，编号为 $1$ 到 $n$，且以节点 $1$ 为根。对于每个 $i$ ($2 \le i \le n$)，节点 $p_i$ 是节点 $i$ 的父节点。树上装饰得很漂亮，节点 $i$ ($1 \le i \le n$) 上有 $a_i$ 个装饰品。

图 D.1：圣诞树

然而，圣诞节已经过去几个月了，是时候取下所有的装饰品，把树收起来留到明年了。由于这个过程很枯燥，你决定通过仅使用以下操作（可以执行零次或多次）来让它变得更有趣：

选择一个节点 $u$。对于从节点 $1$ 到节点 $u$ 的唯一简单路径上的每个节点 $v$（包括端点），如果 $v$ 上还有装饰品，则从 $v$ 上恰好移走一个装饰品。

当你还在计算所需的最少操作次数时，你的小孩修改了树上的装饰品数量。更具体地说，你的孩子进行了 $q$ 次修改。在第 $j$ 次修改中，节点 $u_j$ 上的装饰品数量被修改为 $x_j$ ($1 \le j \le q$)。请注意，这些修改是持久的；每次修改的效果都会累积到后续的修改中。

请注意，你实际上并不需要在树上执行任何操作。

你的任务是，针对初始状态以及每次修改之后，确定在当前时刻移走树上所有装饰品所需的最少操作次数。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。接下来是 $t$ 个测试用例，每个测试用例的格式如下。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 200\,000$；$1 \le q \le 200\,000$)。

第二行包含 $n - 1$ 个整数 $p_2, p_3, \dots, p_n$（对于所有 $2 \le i \le n$，满足 $1 \le p_i < i$）。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（对于所有 $1 \le i \le n$，满足 $1 \le a_i \le 10^9$）。

接下来的 $q$ 行中，第 $j$ 行包含两个整数 $u_j$ 和 $x_j$ ($1 \le u_j \le n$；$1 \le x_j \le 10^9$)。

单个输入文件中所有测试用例的 $n$ 之和不超过 $200\,000$。

单个输入文件中所有测试用例的 $q$ 之和不超过 $200\,000$。

输出格式

对于每个测试用例，输出 $q + 1$ 行。第一行应包含初始树所需的最少操作次数。接下来的 $q$ 行中，第 $j$ 行应包含第 $j$ 次修改发生后所需的最少操作次数。

样例

输入样例 1

2
6 3
1 1 2 3 3
5 3 2 5 2 4
4 1
3 10
1 6
8 6
1 2 3 4 5 5 3
1 1 1 1 1 1 1 1
6 3
8 3
5 5
6 1
3 7
5 1

输出样例 1

11
9
13
13
3
5
7
8
8
8
7

说明

对于第一个测试用例，其初始树如图 D.1 所示。请注意，图中节点 1 处的星星也是一个装饰品。

• 在初始树中，你可以通过选择节点 4 五次、节点 5 两次、节点 6 四次，共 11 次操作来移走所有装饰品。
• 第一次修改后，节点 4 上只有一个装饰品。你需要 9 次操作：选择节点 4 一次、节点 2 两次、节点 5 两次、节点 6 四次。
• 第二次修改后，节点 3 上有十个装饰品。你需要 13 次操作。
• 第三次修改后，节点 1 上有六个装饰品。然而，所需的操作次数保持不变。