Desendants

众所周知，染染的家族非常庞大。

染染所在的家族有 $n$ 个男性，男性 $1$ 是他们家族中可追溯的辈分最大的男性，而剩余的男性 $i\,\,(2\leq i\leq n)$ 的爹是男性 $f_i$。由于这是一个家族，我们保证染染家族的所有人的祖辈都可以追溯到男性 $1$。

染染的家族有一个特殊的传统：时不时会有某个人给自己往后若干代的后代（只包含那一代）奖励，方便起见，我们用一个整数来代表某次奖励的价值。

具体来说，根据族谱的记载，总共进行了 $q$ 次这样的传统，按时间顺序第 $i$ 次进行这样的传统的是男性 $x_i$，他对他的所有 $k_i$ 代后代（自己算 $k_i=0$，儿子算 $k_i=1$）进行了价值 $v_i$ 的奖励。

而染染想要在每条族谱的记载后知道，男性 $x_i$ 的所有 $k_i$ 代后代到这条记载为止所受奖励的价值的总和。

输入第 $1$ 行 $1$ 个整数 $T$，表示数据组数。

对于每组数据，第 $1$ 行 $2$ 个整数 $n,q$，代表染染家族的男性数量和族谱上的记载数量。

第 $2$ 行 $n-1$ 个整数 $f_2,f_3,\cdots,f_n$，表示除男性 $1$ 外每个男性的爹。

接下来 $q$ 行，第 $i$ 行三个整数 $x_i,k_i,v_i$，表示按时间顺序族谱上的第 $i$ 条记载。

#### 评测数据规模

对于所有测评数据，$1\leq T\leq 5$，$1\leq n,q\leq 10^5$，$1\leq f_i,x_i\leq n$，$0\leq k\leq n$，$|v_i|\leq 10^9$。

对于每组数据输出 $q$ 行，第 $i$ 行表示第 $i$ 条记载对应的答案。

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

4
8
0
3
14
5
2
0

2024杭电ACM-个人PK赛（2）