You are given a static tree with n nodes. Each node has an integer value.

You need to answer q queries. For each query (u, v), find the maximum node value on the unique path from node u to node v, including both endpoints.

There are no updates to the tree.

Because the number of queries can be very large, your solution should efficiently answer path queries.

Input Format

n q

a1 a2 ... an

u1 v1

u2 v2

... uq vq

n = number of nodes

q = number of queries

ai = value of node i

Next n-1 lines contain the edges:

u v

Next q lines contain queries (u, v).

Constraints

1 ≤ n ≤ 2 × 10^5

1 ≤ q ≤ 2 × 10^5

1 ≤ ai ≤ 10^9

1 ≤ u, v ≤ n

The tree contains exactly n-1 edges.

Output

For every query, print the maximum value on the path.

Test Case 1

5 3

5 2 9 1 7

1 2

1 3

2 4

2 5

1 4

4 5

3 4

Tree:

    1(5)
   /   \
2(2)   3(9)
/ \

4(1) 5(7)

Queries:

1 → 4: values 5, 2, 1 → 5

4 → 5: values 1, 2, 7 → 7

3 → 4: values 9, 5, 2, 1 → 9

Output:

5

7

9

Expected Approach

Heavy-Light Decomposition + Segment Tree