给你一棵有根树，节点的编号为 \(1,\dots,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\) 值的和。

第一行一个正整数 \(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 \leq 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)\) 的操作，操作的含义见题目描述。

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

样例解释
每次操作之后 \(g_5\) 的值依次为 \(5, 5, 6, 6, 7, 7\) 。

测试数据由deaf提供(只有1组极限的数据)