Xiao Z has a tree with $n$ nodes, rooted at node $1$, where all edge weights are $1$. Each node $x$ has a weight $a_x$, and initially, the weights of all nodes are $0$.

Xiao Z wants to perform a total of $m$ operations on this tree and wishes to support the following four types of operations:

1. Given $x, y, k, v$, add $v$ to the weight of all nodes $i$ such that the shortest distance between node $i$ and the unique shortest path $(x, y)$ on the tree is $\leq k$. That is, $a_i \leftarrow a_i + v$.
2. Given $x, v$, add $v$ to the weight of all nodes $i$ in the subtree of $x$. That is, $a_i \leftarrow a_i + v$.
3. Given $x, y, k$, query the sum of weights of all nodes $i$ such that the shortest distance between node $i$ and the unique shortest path $(x, y)$ on the tree is $\leq k$.
4. Given $x$, query the sum of weights of all nodes $i$ in the subtree of $x$.

Since the answers can be large, output the results modulo $2^{64}$.

Input

The first line contains two positive integers $n$ and $m$.

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

The next $m$ lines each start with an operation type $op$.

• When $op=1$, $x, y, k, v$ are given to describe operation 1.
• When $op=2$, $x, v$ are given to describe operation 2.
• When $op=3$, $x, y, k$ are given to describe operation 3.
• When $op=4$, $x$ is given to describe operation 4.

Output

For each operation 3 and operation 4, output the corresponding answer modulo $2^{64}$.

Constraints

$1 \leq n, m \leq 2 \times 10^5$, $1 \leq x, y \leq n$, $1 \leq v \leq 10^9$, $0 \leq k \leq 3$.

Subtasks

• Subtask 1 (10 points): $1 \leq n, m \leq 5 \times 10^3$.
• Subtask 2 (10 points): $k=0$.
• Subtask 3 (5 points): The tree is guaranteed to be a chain where $1$ is connected to $2$, $2$ to $3$, ..., $n-1$ to $n$ (all edges are of the form $i$ connected to $i+1$).
• Subtask 4 (10 points): $k=1$, only operations 1 and 3 are used, and for these operations $x=y$ (the modified/queried path is a single point).
• Subtask 5 (10 points): Only operations 1 and 3 are used, and for these operations $x=y$ (the modified/queried path is a single point).
• Subtask 6 (15 points): For operations 1 and 3, $x=y$ (the modified/queried path is a single point).
• Subtask 7 (15 points): $k \leq 1$.
• Subtask 8 (25 points): No special constraints.