Given a tree with $n$ vertices and rooted at $1$. Each vertex has an initial value, and initially, all these values are $0$.
There are $q$ queries of two types:
- `1 u`: Find the sum of values of vertices in the subtree rooted at $u$.
- `2 u`: Find the value at vertex $u$.
- `3 u v x`: Increase the values of vertices on the simple path from $u$ to $v$ by $x$.
Answer the queries of types $1$ and $2$.
### Input
- The first line contains two integers $n$ and $q$.
- The next $n - 1$ lines each contain two integers $u$ and $v$, indicating an edge between $u$ and $v$.
- The next $q$ lines each contain a query in the specified format.
### Output
- Print an integer as the answer for each query of types $1$ and $2$.
### 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
3 2 4 2
2 5
1 5
1 2
1 5
1 1
2 2
3 4 4 4
2 3
1 2
```
Output:
```
0
0
4
0
4
2
0
8
```