You are given a one-indexed tree of nodes and edges. Each node has a weight .

Your friend asks you questions with regards to the structure of the tree of the following forms:

`1 r k`

If the*root*of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the*sum*of all the weights in that subtree?`2 r k`

If the*root*of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the*maximum*of all the weights in that subtree?

It is guaranteed that . Recall that there is always exactly subtrees in a tree. The heaviest subtree is out of *all* the subtrees, not just ones rooted at the children of the root.

Can you answer these questions for your friend?

#### Input Specification

The first line will contain two integers .

The next line will contain integers, .

The next lines will each contain two integers, , indicating that nodes and are connected by an edge. It is guaranteed that the entire tree is connected.

The next lines will each contain a question as defined above.

#### Output Specification

For each question, output the heaviness of the heaviest subtree if the root of the tree is node , where the definition of heaviness is dependant on the query form.

#### Subtasks

##### Subtask 1 [14%]

##### Subtask 2 [39%]

There will only be type `1`

queries.

##### Subtask 3 [47%]

No additional constraints.

#### Sample Input For Subtask 1

```
7 5
5 3 -2 4 -1 0 -2
1 2
1 3
2 7
3 4
3 5
5 6
1 1 3
2 1 3
1 4 5
2 5 7
2 7 4
```

#### Sample Output For Subtask 1

```
1
4
0
-2
4
```

#### Sample Input For Subtask 2

```
6 4
-2 -1 5 -3 2 4
1 2
1 3
3 4
4 5
4 6
1 4 5
1 4 1
1 6 2
1 6 6
```

#### Sample Output For Subtask 2

```
-1
5
2
-3
```

#### Sample Input For Subtask 3

```
20 10
13 17 -7 -14 -5 11 -10 3 -4 8 -17 3 5 5 1 6 5 -9 0 -19
2 1
3 2
4 3
5 3
6 2
7 2
8 7
9 6
10 2
11 1
12 2
13 4
14 6
15 1
16 13
17 8
18 11
19 13
20 10
2 13 3
2 13 6
2 1 18
1 16 9
1 11 10
2 1 2
2 6 15
2 12 15
1 5 8
2 4 4
```

#### Sample Output For Subtask 3

```
17
11
-9
-2
1
17
0
0
3
13
```

## Comments