You are given an undirected tree with $$N$$ nodes and the tree is rooted at node 1. Each node has an integer value $$A[i]$$ associated with it represented by an array $$A$$ of size $$N$$.

Also, you are given $$Q$$ queries of the following type:

$$u$$ $$v$$: Find the value of Minimum + Maximum + Median of all the values present on the simple path between node $$u$$ and node $$v$$.
Suppose, $$K$$ nodes are present on the simple path, then Median is defined as \(((K+1) / 2)^{th}\) smallest element present on the simple path.

Input format

The first line contains two space-separated integers $$N$$, $$Q$$ denoting the number of nodes and queries respectively.
The second line contains $$N$$ space-separated integers denoting array $$A$$.
Next $$N - 1$$ lines contain two space-separated integers denoting the edges of the tree.
Next $$Q$$ lines contain two space-separated integers denoting the queries.

Output format

Print $$Q$$ space-separated integers denoting the answer of queries.

Constraints

\(1 \le N \le 4 \times 10^4 \\ 1 \le Q \le 10^5 \\ 1 \le A[i] \le 10^6 \\ \)