背景

sro ZHX orz
ZHX也有一颗知识树
随着ZHX的学习，知识的掌握发生变化
SBW想知道ZHX知识掌握情况，于是向你求助
并答应告诉你ZHX究竟在学习什么

描述

给出一棵N个点、以1为根的树，点有点权
M个操作，7个操作类型
类型1为某条路径上的点权变化
类型2为某棵子树上的点权变化
类型3为询问某点点权
类型4为询问某路径上点权和
类型5为询问某子树上点权和
类型6为询问某路径上点权最大值
类型7为询问某子树上点权最大值

输入

第一行两个数N, M
第二行N个数为初始各点点权ai
接下来N-1行，每行两个数X, Y，表示树中有一条边连接点X与点Y
接下来M行，每行若干个数，表示一个操作
(opt==1) opt, x, y, v
(opt==2) opt, x, v
(opt==3) opt, x
(opt==4) opt, x, y
(opt==5) opt, x
(opt==6) opt, x, y
(opt==7) opt, x
(opt表示操作类型)

输出

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

样例

输入

4 7
1 2 3 4
2 1
3 1
4 3
1 2 3 1
2 3 1
3 3
4 1 4
5 1
6 4 1
7 2

输出

5
12
15
5
3

范围

10% N,M<=5
20% N,M<=10
60% N,M<=3000 |ai|<=100
80% N,M<=\(10^5\)
100% 1<=N,M<=\(10^6\) |ai|<=5000 1<=opt<=7 1<=x,y<=N |v|<=50

限制

5000ms
512M