J. 合二为一
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有 $$$n$$$ 种材料，分别编号为 $$$1$$$ 到 $$$n$$$。材料 $$$i$$$ 的价格为 $$$c_i$$$。

材料之间的依赖关系构成一棵以材料 $$$1$$$ 为根的有根树：对于每个材料 $$$i$$$（$$$2 \le i \le n$$$），它恰有一个「下游材料」$$$f_i$$$（$$$1 \le f_i \lt i$$$）。如果 $$$f_y = x$$$，则称材料 $$$y$$$ 是材料 $$$x$$$ 的「上游材料」。

你需要依次处理 $$$q$$$ 次事件，事件分为以下两种：

  • 「价格更新」：给定 $$$u$$$ 和 $$$x$$$，将材料 $$$u$$$ 的价格 $$$c_u$$$ 修改为 $$$x$$$；
  • 「合成询问」：给定 $$$u$$$，求获得一份材料 $$$u$$$ 的最小总花费。你可以进行任意多次以下两种操作，顺序任意：
    • 「购买」：选择一种材料 $$$x$$$（$$$1 \le x \le n$$$），花费 $$$c_x$$$ 获得一份材料 $$$x$$$；
    • 「合成」：若材料 $$$x$$$ 和材料 $$$y$$$（$$$x \ne y$$$）的「下游材料」相同（即 $$$f_x = f_y$$$），则可以消耗一份材料 $$$x$$$ 和一份材料 $$$y$$$，免费获得一份材料 $$$f_x$$$。「合成」得到的材料可以继续参与之后的操作。

「价格更新」会对此后的所有事件产生影响；每次「合成询问」相互独立：询问开始时你没有任何材料，询问过程中获得的材料不会保留到之后的事件中。

对于每次「合成询问」，输出获得一份材料 $$$u$$$ 的最小总花费。

Input

第一行两个整数 $$$n$$$ 和 $$$q$$$（$$$2 \le n, q \le 10^{6}$$$），分别表示材料的种类数和事件的数量。

第二行 $$$n$$$ 个整数 $$$c_1, c_2, \ldots, c_n$$$（$$$0 \le c_i \le 10^{18}$$$），表示每种材料的初始价格。

第三行 $$$n - 1$$$ 个整数 $$$f_2, f_3, \ldots, f_n$$$（$$$1 \le f_i \lt i$$$），其中 $$$f_i$$$ 表示材料 $$$i$$$ 的「下游材料」。

接下来 $$$q$$$ 行，每行描述一个事件，格式为以下两种之一：

  • $$$1 \ u \ x$$$（$$$1 \le u \le n$$$，$$$0 \le x \le 10^{18}$$$），表示一次「价格更新」；
  • $$$2 \ u$$$（$$$1 \le u \le n$$$），表示一次「合成询问」。
Output

对于每次「合成询问」，输出一行，包含一个整数，表示该次询问的答案。

可以证明，答案不超过 $$$10^{18}$$$。

Example
Input
6 11
2 1 0 6 0 9
1 1 3 3 3
2 1
1 6 6
1 5 1
2 6
2 3
1 3 9
1 4 7
1 2 6
2 3
1 1 5
2 1
Output
1
6
0
7
5
Note

样例中，材料 $$$2$$$、$$$3$$$ 的「下游材料」均为材料 $$$1$$$，材料 $$$4$$$、$$$5$$$、$$$6$$$ 的「下游材料」均为材料 $$$3$$$。

对于第一次「合成询问」，可以直接花费 $$$c_1 = 2$$$ 购买材料 $$$1$$$；也可以花费 $$$1$$$ 购买材料 $$$2$$$、花费 $$$0$$$ 购买材料 $$$3$$$，随后将二者免费合成为材料 $$$1$$$。后者总花费为 $$$1 + 0 = 1$$$，因此答案为 $$$1$$$。

对于第二次「合成询问」，此前的两次「价格更新」已将 $$$c_6$$$、$$$c_5$$$ 分别修改为 $$$6$$$、$$$1$$$。材料 $$$6$$$ 没有「上游材料」，无法通过「合成」获得，只能花费 $$$6$$$ 直接购买，因此答案为 $$$6$$$。

对于第三次「合成询问」，直接花费 $$$c_3 = 0$$$ 购买材料 $$$3$$$ 即可，因此答案为 $$$0$$$。

对于第四次「合成询问」，此时 $$$c_3 = 9$$$、$$$c_4 = 7$$$、$$$c_5 = 1$$$、$$$c_6 = 6$$$。最优方案是花费 $$$1$$$ 购买材料 $$$5$$$、花费 $$$6$$$ 购买材料 $$$6$$$，再将二者免费合成为材料 $$$3$$$，总花费 $$$1 + 6 = 7$$$，小于直接购买的 $$$9$$$。可以证明不存在总花费更小的方案，因此答案为 $$$7$$$。

对于第五次「合成询问」，此时 $$$c_1 = 5$$$；若通过「合成」获得材料 $$$1$$$，需要一份材料 $$$2$$$ 和一份材料 $$$3$$$，至少花费 $$$6 + 7 = 13$$$，大于直接购买的 $$$5$$$，因此答案为 $$$5$$$。