Backgrounds

小D是一个胆小的女孩，她最讨厌的东西就是毛毛虫。因为一般情况下毛毛虫都在树上所以这题和树有关。

Description

给定一颗有$3\le n\le 100000$有初始点权，边权为1的以1为根的树。

定义树上u到v的路径是集合$\text{Path}(u,v)$，由路径上的点构成。

定义毛毛虫路径是集合$\text{Worm}(u,v)$，满足$\forall x \in \text{Worm}(u,v)\exist y \in \text{Path}(u,v)$中x到y的最短距离$\le 1$。

• a=1，子树修改。将一个点的子树中所有点加上一个值。
• a=2，子树查询。输出一个点的子树的权值和$\text{mod}\quad 2^{32}$。
• a=3，毛毛虫路径修改。将$\text{Worm}(u,v)$ 所有的点加上一个值。
• a=4，毛毛虫路径查询。输出$\text{Worm}(u,v)$ 所有的点的权值和$\text{mod}\quad 2^{32}$。

但是她早就是地表最强选手所以她当然会这道题啦。小D其实早就【数据删除】你了，所以她决定考验一下你会不会做。问题现在就交给你啦! 你不应该吊打妹子，所以你不能吊打std(出题人不是妹子)

Input Format

第一行三个正整数整数$n,m$分别表示点的个数和询问的个数。

接下来一行$n$个非负整数表示初始点权$w_i$

接下来$n-1$行每行恰好两个正整数，分别表示一条边的两个端点。

接下来$m$行每行恰好三个正整数，表示询问，保证$u, v\in[1,n]$，保证$w< 2^{31}$。

n m
w_i ...
u v
...
1 u w
2 u
3 u v w
4 u v 
...

保证输入数据构成一棵树。

Output Format

你需要输出恰好$m$行非负整数，依次表示第$i$次询问的答案。

ans_1
...

Input Sample

5 4
10 45 32 16 5 
2 1
2 4
2 3
1 5
1 4 3
2 4
3 1 2 5
4 1 3

Output Sample

19
136

Constraints

Hint

精心构造的数据，hack了所有的暴力，放心地投入此题吧，会有收获的。一定能区分出 万众瞩目 的你。