Problem Description

给你一棵有根树，节点的编号为$1,\ldots, n$，其中节点$1$为根。每个点有个点权$f_i$。对于任意一个点$i$，记$g_i$为这个点到根路径上所有点$f$的最大值。你要支持两个操作：

- `1 i v`，表示操作1：将$f_i$修改为$v$。
- `2 i`，表示操作2：求出$i$这个点在这个操作之前，每次操作之后$g_i$的值的和，这里的操作包括修改（操作1）和询问（操作2）。如果这个操作之前没有任何操作，那么和为$0$。

在最后，请对于每个点$i$输出它每次操作之后$g_i$值的和。

Input

第一行一个正整数$T(1\leq T\leq 2)$表示数据组数。

对于每组数据，第一行一个整数$n,q(1\leq n,q \leq 10^5)$，表示点数和操作个数。接下来一行$n-1$个整数$p_2, p_3, \dots, p_n (1\leq p_i < i-1)$，$p_i$表示第$i$个点的父亲。

接下来一行$n$个数$f_1, f_2, \dots, f_n(1\leq f_i\leq 10^9)$表示这$n$个点的初始权值。

接下来$q$行，每行一个形如`1 i v`$(1\leq i\leq n, 1\leq v\leq 10^9)$或者`2 i`$(1\leq i \leq n)$的操作，操作的含义见题目描述。

Output

对于每组数据，对于其中每个询问操作，输出一行，表示这个询问的答案。接下来按照$i$从$1$到$n$的顺序依次输出每个点$i$每次操作之后$g_i$值的和，每行一个数。

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

0
5
16
29
26
28
32
34
36

Hint

每次操作之后g₅的值依次为5, 5, 6, 6, 7, 7。