I. Optimal Tree Exploration
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a rooted tree consisting of $$$n$$$ nodes, where each node $$$i$$$ has an associated value $$$a_i$$$. The tree is rooted at node $$$1$$$. $$$Alice$$$ and $$$Bob$$$ are going to explore this tree multiple times, and you are going to help them by answering their queries.

In the $$$i$$$-th exploration, $$$Alice$$$ starts from node $$$x_i$$$ and $$$Bob$$$ starts from node $$$y_i$$$. Both $$$Alice$$$ and $$$Bob$$$ can move from their current node to a child node if it exists and hasn't been visited by the other player yet. Maintaining these conditions, both of them can move as many times as they want. Note that, $$$Alice$$$ and $$$Bob$$$ do not need to move simultaneously. They can move whenever they wish. Also note that, neither $$$Alice$$$ nor $$$Bob$$$ can move from their current node to any other node except the direct child nodes.

Both $$$Alice$$$ and $$$Bob$$$ want to maximize the value they see on their exploration. Your task is to find the maximum value that $$$Alice$$$ and $$$Bob$$$ can see while exploring the tree if they move optimally.

Note that, each exploration is independent. That is, in each query, they start from the given nodes and there is no relation between queries.

Input

The first line of contains two integers $$$n$$$ and $$$q$$$ $$$(2 \leq n, q \leq 5\cdot10^5)$$$ — the number of nodes in the tree and the number of queries respectively.

The second line contains n space separated integers $$$a_1,a_2,...,a_n \; (0 \leq a_i \leq 10^9)$$$ – the array $$$a$$$

The next $$$n-1$$$ lines describe the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$ — the numbers of the nodes connected by the $$$i$$$-th edge.

Next $$$q$$$ lines describe the queries. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(1 \leq x_i, y_i \leq n, \; x_i \neq y_i)$$$ — the starting node for $$$Alice$$$ and $$$Bob$$$ respectively in this query.

Output

For each query, output two space separated integers — the maximum value $$$Alice$$$ and $$$Bob$$$ can see while exploring the tree.

Example
Input
8 3
3 1 6 8 7 2 4 5
1 2
2 3
1 4
2 5
5 7
3 6
6 8
3 4
2 5
6 1
Output
6 8
6 7
5 8
Note

The tree for the sample test case looks like this:

Consider the first test case:

Alice starts from node $$$3$$$ and Bob starts from node $$$4$$$. Notice that whichever path Alice choose to go in its' subtree does not contain any node that can be in one of the possible path for Bob. Similarly Bob can also choose any path and it will not contain any node that can be in Alice's path. So, the maximum value Alice can observe is $$$6$$$, the value of node $$$3$$$, and maximum value Bob can observe is $$$8$$$, the value of node $$$4$$$.

In the second test case:

Alice starts from node $$$2$$$ and Bob starts from node $$$5$$$. If Alice goes to node 5, he can observe $$$7$$$, but since node $$$5$$$ is already visited by Bob, Alice can not go there. So, Alice can only go in any node of this path $$$2 \rightarrow 3 \rightarrow 6 \rightarrow 8$$$. So, the maximum value for Alice is $$$6$$$, the value of node $$$3$$$. But, Bob can go in any node of its' subtree, so the maximum value for him is $$$7$$$, the value of node $$$5$$$.