Minimum Node Weight on a Path

Problem Description

You are given a tree with $n$ nodes, numbered from $1$ to $n$, each with a node weight $a_i$.

There are $q$ queries. Each query reads two integers $u, v$ and asks: what is the minimum node weight on the path from node $u$ to node $v$?

Input Format

The first line contains two integers $n, q$, the number of vertices and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The following $n-1$ lines each contain two integers $u, v$, meaning there is an edge between node $u$ and node $v$.

The following $q$ lines each contain two integers $u, v$, representing one query.

Output Format

For each query, output one line containing an integer: the answer.

Sample Input

3 3
1 2 3
1 2
2 3
1 2
1 3
2 3

Sample Output

1
1
2

Constraints

For $100\%$ of the data, $1 \leq n, q \leq 10^5, 1 \leq a_i \leq 10^5, 1 \leq u, v \leq n, u \neq v$, and the input is guaranteed to form a tree.