背景

WRX有一颗知识树
随着WRX的成长，知识的掌握发生变化
SBW想知道WRX知识掌握情况，于是向你求助
并答应告诉你WRX手机号的第一位

描述

一棵树，树上N个点，点有点权
M个操作
或为询问某点点权
或为某条路径上的点权变化

输入

第一行两个数N, M
第二行N个数为初始各点点权ai
接下来N-1行，每行两个数X, Y，表示树中有一条边连接点X与点Y
接下来M行，每行四或二个数opt, x(, y, v)
若opt==1，表示x至y最短路径上的点点权增加v
若opt==0，表示询问点x点权

输出

对每个询问，一行一个数表示所问点的点权

样例

输入

3 3
1 2 3
2 1
3 2
1 1 3 -1
0 2
0 3

输出

1
2

范围

8/45 N,M<=10
32/45 N,M<=3000 ai<=1000
36/45 N,M<=100000 ai<=100000
45/45 N,M<=\(10^6\) -\(10^7\)<=ai<=\(10^7\) 1<=x,y<=N -500<=v<=500

限制

3000ms
384M

来源

TJ-YH-LMZ