Your grandparents have decided to come visit you for Christmas! However, you notice that they are squinting as they look at your Christmas tree!

Being the computer science nerd that you are, your Christmas tree is a tree with ~N~ nodes, the ~i^\text{th}~ of which has a light with a brightness of ~c_i~. The similarity of a path is the minimum non-negative difference between the brightnesses of any two distinct nodes on the path. Given that your grandparents look at ~Q~ paths, can you tell them what the similarity of each path is?

Constraints

For all subtasks:
~1 \le c_i \le 10^9~
~1 \le a_i,b_i,u_i,v_i \le N~
~u_i \ne v_i~

Subtask 1 [10%]

~2 \le N, Q \le 100~

Subtask 2 [10%]

~2 \le N, Q \le 3\,000~

Subtask 3 [80%]

~2 \le N, Q \le 50\,000~

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~Q~.
The next line of input will contain ~N~ space-separated integers, ~c_1, c_2, \dots, c_N~.
The next ~N-1~ lines will contain two space-separated integers, ~a_i~ and ~b_i~, indicating that there is an edge between nodes ~a_i~ and ~b_i~.
The next ~Q~ lines will each contain two space-separated integers, ~u_i~ and ~v_i~, indicating that your grandparents look at the path ~u_i~ to ~v_i~.

Output Specification

Output ~Q~ lines. The ~i^\text{th}~ line should contain a single integer: the similarity of the path from ~u_i~ to ~v_i~.

Sample Input

5 3
1 8 7 5 6
2 4
4 1
3 1
1 5
2 3
4 3
5 2

Sample Output

1
2
1