题目描述

瓜瓜有 $n$ 个小球，每个质量为 $m_i$。瓜瓜打算用 $n-1$ 个弹簧连接它们，使其成为一个树，根节点为 $1$。当我们把根节点定在墙上时，小球会竖着垂成一列（不考虑小球和弹簧的大小及碰撞），且弹簧会在重力的作用下形变。

由物理学知识知道，弹簧的形变长度与力成正比。为简单起见，弹簧的原长是 $1$ cm，被施加 $u$ kg 的重力后的长度是 $1 + u$ cm。

不难通过隔离法进行受力分析，节点 $x$ 与其父节点的距离是 $1 + w_x$ cm，其中 $w_x$ 是节点 $x$ 所在子树的质量之和。

瓜瓜觉得这样还难不倒你，又在问题中引入了一些变化。瓜瓜会在树上挂上一个重物，再询问某个节点到根节点的距离。重物只对当前询问有影响。

输入描述

第一行有两个小球 $n, q$，表示有 $q$ 组询问，其中 $1 \leqslant n, q \leqslant 10^5$。

接下来一行有 $n$ 个正整数 $m_1, \cdots, m_n$，表示第 $i$ 个球的质量，并且 $0 \leqslant m_i \leqslant 10^6$。

接下来一行有 $n$ 个正整数，$f_1, \cdots, f_n$，表示第 $i$ 个球在树上的父节点是 $f_i$。保证给出的是合法的树，并且根节点有 $f_1 = -1$。

接下来有 $q$ 行，每行有一个询问，每行有三个正整数 $x, y, u$，表示在节点 $x$ 上挂一个 $u$ kg 的重物，然后询问节点 $y$ 到根节点距离。保证 $1 \leqslant x, y \leqslant n$，且 $0 \leqslant u \leqslant 10^6$。重物只对当前询问有影响。

输出描述

你需要输出 $q$ 行，每行一个整数，表示 $y$ 到根节点的距离。

样例

5 5
1 2 3 4 5
-1 1 1 2 2
5 2 1
4 3 3
3 2 3
1 2 2
2 1 1

13
4
12
12
0

提示

在未挂任何重物时长这样。