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 ~i^\text{th}~ node having value ~v_i~. 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 ~0.5~, it rounds down, and rounds up otherwise.

For example, ~2.5~ rounds to ~3~, and ~4.48~ rounds to ~4~.

Constraints

~1 \le N \le 1\,000~

~1 \le a_i, b_i \le N~

~1 \le Q \le 1\,000~

~1 \le v_i \le 100\,000~

Input Specification

The first line of input will contain two integers, ~N~ and ~Q~.
The second line of input will contain ~N~ space separated integers, ~v_1, v_2, \dots, v_N~.
The next ~N-1~ lines will have two integers, ~a_i~ and ~b_i~, indicating there is an edge between ~a_i~ and ~b_i~.
The next ~Q~ lines will each contain a valid query.

Output Specification

~Q~ 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 ~4~ nodes, so the mean is ~(1+2+3+3)/4=2.25~, which is rounded to ~2~.

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

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

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