A tree is a graph where each node is connected to each other, and there is exactly one path between any two nodes. One day, Jessica gives Roger a tree, with the node having value . She then asks 3 types of queries:

`1 x y`

: Find the mean of all the values of the nodes on the path from`x`

to`y`

, rounded to the nearest integer.`2 x y`

: Find the median of all the values of the nodes on the path from`x`

to`y`

, rounded to the nearest integer.`3 x y`

: Find the mode of all the values of the nodes on the path from`x`

to`y`

. In the case of a tie, print the smallest value.

**Note:** The rules of rounding are as follows: if the decimal part of the number is less than , it rounds down, and rounds up otherwise.

For example, rounds to , and rounds to .

#### Constraints

#### Input Specification

The first line of input will contain two integers, and .

The second line of input will contain space separated integers, .

The next lines will have two integers, and , indicating there is an edge between and .

The next lines will each contain a valid query.

#### Output Specification

lines, the answer to each query.

#### Sample Input

```
4 4
1 2 3 3
1 2
2 3
3 4
1 1 4
2 2 4
3 1 4
3 1 2
```

#### Sample Output

```
2
3
3
1
```

#### Explanation for Sample Output

For the first query, we pass through all nodes, so the mean is , which is rounded to .

For the second query, we pass through the nodes of weight , , and , so their median is .

For the third query, we pass through all nodes. and appear only once but appears twice, so the mode is .

For the last query, we pass through the first two nodes with weight and . Both appear only once, but , so the mode is .

## Comments

This comment is hidden due to too much negative feedback. Show it anyway.

That's still less than 4.5, so it rounds down.