题目背景

  「长养薰风拂晓吹，浅开荷芰落蔷薇」

---

  在校内的最后一次试演出！

  从第一次登台至今，从以往约定的放学后空无一人的操场到如今日夜挥汗的训练室，他们与彼此的约定是否改变呢？

  “肩上的吉他和小小梦想，要为它们长出坚强的翅膀！”

---

  小暑 「Can you hear me now?　我会从此成为你的骄傲　现在就要出发　一切刚刚好」

题目描述

  还记得吗？你可是天依他们的专业分析师。除了演出者的表现，观众们的情感波动也是重要的分析对象。经过不懈努力，你提出了以下这些指标（出题人已经被你消灭啦，但还是请你耐心读题）：

  「情绪」 我们用强烈度 $v\in\mathbb N^\star$ 来表达一个情绪。

  「心境」 一系列情绪共同组成一个心境，我们将心境描述为一个二元组 $M=(s,f)$，其中 $s,f\in\mathbb N^\star$，其中 $s$ 为所含情绪的强烈度之和，$f$ 为某个特征情绪的强烈度。

  「共鸣」 两个心境可以通过共鸣而融合得到新的心境。我们将 $M_2=(s_2,f_2)$ 融合向 $M_1=(s_1,f_1)$ 的共鸣记作 $M_1+M_2$，共鸣的结果是一个新的心境 $M=M_1+M_2=(s_1+s_2,f_1)$。注意此时不一定满足 $M_1+M_2=M_2+M_1$。

  「心路」 在一棵有根树上，沿树形关系共鸣心境的过程称为心路。对于以 $r$ 为根的子树，其心路历程可以描述如下：

1. 初始时，$A_r\gets M_r$，其中 $A_x$ 表示以 $x$ 为根的子树心路完成后的最终心境，$M_x$ 为 $x$ 结点上的初始心境。

2. 按编号升序地枚举 $r$ 的孩子结点 $x$：

   • 递归完成 $x$ 子树的心路，得到 $A_x$。此时，设 $A_r=(s_r,f_r)$，$A_x=(s_x,f_x)$。

   • 若 $s_r\ge s_x$，则令 $A_r\gets A_r+A_x$，否则令 $A_r\gets A_x+A_r$。

  最终的 $A_r$ 即为以 $r$ 为根的子树心路完成后的最终心境。

---

  为研究特定观众的心理变化情况，你需要时刻监控其上述指标。现给定一棵含有 $n$ 个结点，以 $1$ 为根结点的有根树，结点 $x$ 上初始有心境 $M_x=(a_x,a_x)$。此后进行 $q$ 次操作，每次操作有以下两类：

1. 给出结点 $x$，询问 $A_x=(s_x,f_x)$ 中 $f_x$ 的值，其中 $A_x$ 应当在每次询问时，依据当前的信息重新计算。

2. 给出结点 $x$ 和变化量 $d$，令 $a_x\gets a_x+d$，并修改对应的 $M_x$。注意 $d$ 可能为负数，但保证操作前后都有 $a_x>0$。

  请你对于每个询问操作，计算出相应的答案。

输入格式

第一行两个整数 $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

提示

数据规模与约定

对于 $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}$。

对于不同的子任务，作如下约定：

子任务编号	$n$	$q$	特殊性质	子任务分值
$1$	$\leq 10 ^ 3$		无	$10$
$2$	$\leq 2 \times 10 ^ 5$		$\textbf A$	$20$
$3$	$\le 2 \times 10 ^ 5$	$\le 2 \times 10 ^ 5$	$\textbf B$
$4$		$\leq 2 \times 10 ^ 5$	无	$50$

• 特殊性质 $\textbf A$：对于 $i\in[2,n]$，$p_i=i-1$。

• 特殊性质 $\textbf B$：保证当 $1$ 为根时，原树是一棵二叉树。且对于 $i\in[2,n]$，存在一条从 $1$ 到 $i$，经过边数不超过 $20$ 的树上路径。