Given a tree with $n$ vertices rooted at $1$, where each vertex initially has a value of $0$.
There are $q$ queries, each belonging to one of the following two types:
- `1 u x`: Increase the values of vertices in the subtree rooted at $u$ by $x$.
- `2 u x`: Increase the value of vertex $u$ by $x$.
- `3 u v`: Find the sum of values of vertices on the simple path from $u$ to $v$.
Answer the queries of type $3$.
### Input
- The first line contains two integers $n$ and $q$.
- The next $n-1$ lines each contain two integers $u$ and $v$, indicating there is an edge between $u$ and $v$.
- The next $q$ lines each contain a query in the specified format.
### Output
- Print an integer, the answer for each query of type $3$.
### Constraints
- $1 \le n,q \le 2 \times 10^5$.
- $1 \le u, v \le n$.
- $0 \le |x| \le 10^6$.
### Example
Input:
```
5 10
1 2
2 3
2 4
2 5
1 4 -1
2 5 -4
3 4 5
3 2 5
3 2 2
3 4 2
2 5 5
3 1 2
1 3 3
3 2 1
```
Output:
```
-5
-4
0
-1
0
0
```
