You are given an undirected tree \(T\) with \(N\) nodes rooted at node \(1\). Every node is assigned a value denoted by \(A[i]\).

You are given \(Q\) queries of type:

• \(u \ v\): Print the maximum value of the node present on a simple path between node \(u\) and \(v\) .

Input format

• The first line contains two space-separated integers \(N \ Q\) denoting the number of nodes and queries respectively.
• Next line contains space-separated integers denoting array \(A\).
• Next \(N - 1\) lines contain two space-separated integers \(a \ b\) denoting an edge between node \(a\) and \(b\).
• Next \(Q\) lines contain two space-separated integers \(u \ v\) denoting the query.

Output format

For each query, print the required answer in a new line.

Constraints 

\(1 \le N, Q \le 5 \times 10^5 \\ 1 \le A[i] \le 10^9 \\ 1 \le a, b \le N \\ 1 \le u,v \le N \)

Subtasks

For \(40\%\) score: \(1 \le N, Q \le 10^3\)