Given a rooted tree with $n$ vertices rooted at vertex $1$, where each vertex holds an integer.
You are given $q$ queries, each of which is one of the following 3 types:
- `1 u`: Change the root of the tree to vertex $u$.
- `2 u v x`: Add $x$ to all vertices in the **smallest subtree** that contains both $u$ and $v$.
- `3 u`: Compute the sum of the values of all vertices in the subtree rooted at $u$.
### Input
- The first line contains two integers $n$, $q$.
- The second line contains $n$ integers representing the initial values at the vertices.
- The next $n - 1$ lines each contain two integers $u$, $v$ indicating an edge between $u$ and $v$.
- The next $q$ lines contain the queries.
### Output
- For each query of type `3`, output a single integer which is the answer.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le u, v \le n$.
- $|x| \le 10^6$.
- The absolute value of the integers on the vertices does not exceed $10^6$.
### Example
Input:
```
4 6
4 3 5 6
1 2
2 3
3 4
1 3
2 2 4 3
3 3
1 1
2 2 4 -3
3 2
```
Output:
```
30
14
```
