Little C has built a tree-based data structure to store problems and wants you to help him maintain it.

This data structure is a tree, where each node contains a Binary Search Tree (BST, specifically a non-rotating balanced tree).

The following operations are supported:

1 u v x: Little C has created a problem with difficulty $x$. Select all nodes on the path from $u$ to $v$ in the tree, and insert $x$ into the BST of each of these nodes. It is guaranteed that all $x$ values are distinct.

The pseudocode for inserting into the BST is as follows:

void insert(int&p,int x){
    if(!p) return p=x,void();
    if(x<p) insert(ch[p][0],x);
    else insert(ch[p][1],x);
}

0 u w: Little C wants to search for a value $w$ in the BST at node $u$. If $w$ is found, return the node containing $w$; otherwise, return the node that would be visited just before entering an empty node.

The pseudocode for searching is as follows:

int ask(int p,int x){
    if(x==p) return x;
    if(x<p) return ch[p][0]?ask(ch[p][0]):p;
    else return ch[p][1]?ask(ch[p][1]):p;
}

Let the found position be $x$. Little C wants to form a mock contest using the problems located at the ancestors of $x$ (including $x$ itself) in the BST of node $u$. He wants to calculate the total difficulty of the mock contest. Please output the sum of the difficulties of the problems located at the ancestors of $x$ (including $x$ itself) in the BST of node $u$.

Note that if the BST is empty, please output $0$.

Input

The first line contains $n$ and $m$, representing the number of nodes in the tree and the number of operations, respectively.

The next $n-1$ lines each contain two integers $u$ and $v$, representing an edge in the tree.

The next $m$ lines each contain either 1 u v x or 0 u w, representing an operation.

Output

Output several lines. For each 0 u w operation, output one line representing the answer.

Examples

Input 1

3 10
1 2
2 3
1 1 2 2
1 1 3 1
1 2 3 3
0 1 1
0 1 2
0 2 1
0 2 2
0 2 6
0 3 1
0 3 4

Output 1

3
2
3
2
5
1
4

Input 2~5

See the provided files.

Constraints

For all data: $1\le n,m,x,w\le 2\times 10^5$.

Note: UOJ is missing submissions.