题目描述

"奋战三星期，造台计算机"。小 G 响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小 G 的计算姬可以解决这么个问题：给定一棵 $n$ 个节点的带权树，节点编号为 $1$ 到 $n$，以 $root$ 为根，设 $sum_p$ 表示以点 $p$ 为根的这棵子树中所有节点的权值和。

计算姬支持下列两种操作：

1. 给定两个整数 $u,v$，修改点 $u$ 的权值为 $v$。

2. 给定两个整数 $l,r$，计算 $\sum\limits_{i=l}^rsum_i$。

尽管计算姬可以很快完成这个问题，可是小 G 并不知道它的答案是否正确，你能帮助他吗？

输入格式

第一行两个整数 $n,m$，表示树的节点数与操作次数。
接下来一行 $n$个整数，第 $i$ 个整数 $d_i$ 表示点 $i$ 的初始权值。
接下来 $n$ 行每行两个整数 $a_i,b_i$，表示一条树上的边，若 $a_i=0$ 则说明 $b_i$ 是根。
接下来 $m$ 行每行三个整数，第一个整数 $op$ 表示操作类型。 若 $op=1$ 则接下来两个整数 $u,v$ 表示将点 $u$ 的权值修改为 $v$ 。若 $op=2$ 则接下来两个整数 $l,r$ 表示询问。

输出格式

对每个操作类型 $2$ 输出一行一个整数表示答案。

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

16
10
9

数据规模与约定

对于 $100\%$ 的数据，$1\le n,m\le 10^5$，$1\le d_i,v\lt 2^{31}$，$1\le l\le r\le n$，$1\le u \le n$。