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
nodes, the
of which has a light with a brightness of
. 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
paths, can you tell them what the similarity of each path is?
Constraints
For all subtasks:



Subtask 1 [10%]

Subtask 2 [10%]

Subtask 3 [80%]

Input Specification
The first line of input will contain two space-separated integers,
and
.
The next line of input will contain
space-separated integers,
.
The next
lines will contain two space-separated integers,
and
, indicating that there is an edge between nodes
and
.
The next
lines will each contain two space-separated integers,
and
, indicating that your grandparents look at the path
to
.
Output Specification
Output
lines. The
line should contain a single integer: the similarity of the path from
to
.
Sample Input
Copy
5 3
1 8 7 5 6
2 4
4 1
3 1
1 5
2 3
4 3
5 2
Sample Output
Copy
1
2
1
Comments