#1711. 普通计算姬

普通计算姬

Description

"奋战三星期,造台计算机"。小G响应号召,花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些

。普通计算机能计算数列区间和,而普通计算姬能计算树中子树和。更具体地,小G的计算姬可以解决这么个问题

:给定一棵n个节点的带权树,节点编号为1到n,以root为根,设sum[p]表示以点p为根的这棵子树中所有节点的权

值和。计算姬支持下列两种操作:

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

2 给定两个整数l,r,计算sum[l]+sum[l+1]+....+sum[r-1]+sum[r]

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

Format

Input

第一行两个整数n,m,表示树的节点数与操作次数。

接下来一行n个整数,第i个整数di表示点i的初始权值。

接下来n行每行两个整数ai,bi,表示一条树上的边,若ai=0则说明bi是根。

接下来m行每行三个整数,第一个整数op表示操作类型。

若op=1则接下来两个整数u,v表示将点u的权值修改为v。

若op=2则接下来两个整数l,r表示询问。

N<=10^5,M<=10^5

0<=Di,V<2^31,1<=L<=R<=N,1<=U<=N

Output

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

Samples

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