背景

张船长继一收一组破后，又习得了一收一行破
张船长需要多加练习，于是召集船只进行演习
船只组成了一颗树（以1为根），张船长每次可以收掉固定深度的船
为模拟真实情况，树上某路径上的点船数会变化

描述

给出一棵树，N个点，点有点权即该点船数
M个操作
1 a b 表示a-b这条路径上的各点船数+1
0 d 表示张船长想知道此时收d深度点的船能收多少

输入

第一行：两个正整数N、M
第二行：N个数V_1、V_2、...、V_N为各点初始船数
接下来N-1行：每行两个整数a、b表示树上的一条边
接下来M行：每行一个操作

输出

对于一个0 d操作输出d深度点船数和

样例1

输入

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

输出

8
18
2
3
0

范围

25% 1<=N,M<=5
50% 1<=N,M<=10
65% 1<=N,M<=100
85% 1<=N,M<=1000
95% 1<=N,M<=100000
100% 1<=N,M<=200000 1<=V_i<=300 1<=a,b<=N 1<=d<=2000

限制

1000ms
128M