Background

树剖

Description

给定一个n个点的树，支持链加，链最大，子树加，子树最大。（1号点为root）

Input

第一行两个数n，m表示结点数和操作次数。
下n-1行每行2个数表示边。
下面m行，每行一个opt，
opt=1是链加操作，接下来三个数u,v,x，表示u-v链上加上x；
opt=2是查询链最大，接下来两个数u,v表示查询u-v链最大。
opt=3是子树加，接下来两个数u，x，表示u的子树加x；
opt=4是查询子树最大，接下来一个数u，表示查询u的子树最大。

Output

对于每个询问，输出一行表示答案。

Sample 1

Input

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

Output

5
10
10

Limitation

0.6s，256MB

Hint

对于20%的数据，n<=5000,m<=5000;
对于60%的数据，n<=50000,m<=50000;
对于100%的数据，n<=300000,m<=300000。
操作中的|x|<=1000。