给定树上 $n$ 个点，每个点有一个点权 $v_i$。

在此题面中，启发式合并指，递归地进行从底往上的集合合并，每一次以集合的点权和为键值，将权值和更小的集合中的点加入更大的权值和的集合中，初始时每个点集合为该点本身。

同时我们钦定如下的枚举顺序：假设已经递归进行了所有子树的合并，合并当前层节点时从子树的根开始，将儿子们按编号大小从小到大排序，每一次合并两两集合得到子树的集合。

同时，若两个集合的权值和相同，以集合中最小节点深度为第二关键字进行比较（深度大的向深度小的合并）。

钦定该树的根为 $1$。给出以下查询和修改操作：

1 x 表示查询当前以 $x$ 为根的子树进行启发式合并后，没有进行「合并入另外一个集合」操作的节点权值。

2 x d将第 $x$ 个点的节点权值加 $d$。

输入格式

第一行两个整数 $n,q$，分别表示树的大小和操作次数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示结点 $i$ 的初始权值。

第三行 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$，其中 $p_i$ 表示以结点 $1$ 为根时，结点 $i$ 的父亲。

接下来 $q$ 行，每行格式形如 1 x 或 2 x d，分别对应题目描述中的两种操作。

输出格式

对于每个类型为 $1$ 的操作，输出一行一个整数，表示所求答案。

样例数据

样例输入

5 10
2 10 1 10 3
1 2 3 2
2 1 3
1 3
1 5
2 3 5
2 3 2
1 5
2 5 6
1 3
2 5 -1
2 3 0

样例输出

10
3
3
10

子任务

Idea：FutaRimeWoawaSete，Solution：zhoukangyang，Code：Rainybunny，Data：FutaRimeWoawaSete/Rainybunny

对于 $100\%$ 的数据，$1\le n,q\le2\times10^5$，$1\le p_i < i$；操作给出的 $x\in[1,n]$，$d\in[-10^{18},10^{18}]$；在任意时刻 $a_x\ge 1$ 且 $\sum_{x=1}^na_x\le10^{18}$。