Description

Sxyz里有一群sx。

在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。

为了让花老师开花，这群sx都很努力地发言。

一次xbj对树很关心，总想有一道树的好题目

所以大家就开始讨论有什么树的好操作。

为了让题目变的简单，花老师开始就规定了是有根树。

何其蛙：子树修改，加一个数什么的，显然是可做的。

Dj：换根不是超开心？

Dd：什么子树min，max也不错啊。

Zzw：链上询问min也放进去吧。

Wyk: 链max当然的吧。

Xbj：如果不能换父亲就太无聊了吧。

Gy：链加。

Monkey：链上和。

Shjj：链上修改。

Wtd：子树加。

Sone: 在线就不说什么了吧...

.............

最后大家发现有这道题目有点麻烦..都懒得写，又由于sone最近被3083的遥远的国度中lct被树剖虐暴了..就担任了出题活动.......

Format

Input

第一行是N和M，表示有这棵树有N个点M个询问

然后是N-1行，每行x,y表示x-y有一条边

接下去是N行，每行是一个数字，表示每个点的权值

后面一行表示根

接下来是M行

第一个数字是K

K=0 表示子树修改，后面x,y，表示以x为根的子树的点权值改成y

K=1 表示换根，后面x，表示把这棵树的根变成x

K=2 表示链修改，后面x,y,z，表示把这棵树中x-y的路径上点权值改成z

K=3 表示子树询问min，后面x，表示以x为根的子树中点的权值min

K=4 表示子树询问max，后面x，表示以x为根的子树中点的权值max

K=5 表示子树加，后面x,y，表示x为根的子树中点的权值+y

K=6 表示链加，后面x,y,z，表示把这棵树中x-y的路径上点权值改成+z

K=7 表示链询问min，后面x,y，表示把这棵树中x-y的路径上点的min

K=8 表示链询问max，后面x,y，表示把这棵树中x-y的路径上点的max

K=9 表示换父亲，后面x,y，表示把x的父亲换成y，如果y在x子树里不操作。

K=10 表示链询问sum，后面x,y,z，表示表示把这棵树中x-y的路径上点的sum

K=11 表示子树询问sum，后面x，表示以x为根的子树的点权sum

Output

对于每个询问输出一个答案。

Samples

Input1:

5 5

2 1

3 1

4 1

5 2

4

1

4

1

2

1

10 2 3

3 1

7 3 4

6 3 3 2

9 5 1

 

Input2:

10 12

2 1

3 2

4 2

5 3

6 4

7 5

8 2

9 4

10 9

791

868

505

658

860

623

393

717

410

173

4

0 8 800

1 4

2 8 2 103

3 9

4 4

5 7 304

6 8 8 410

7 10 8

8 1 8

9 6 9

10 2 3

11 5

Output1:

9

1

1

Output2:

173

860

103

791

608

1557

Limitation

数据范围：

N,M<=100000

中间所有的值计算在c++的int内