You are given a rooted tree with N vertices (numbered 1 through N); vertex 1 is the root. Each vertex has a weight; let's denote the weight of vertex i by w_i.

You should answer Q queries. The queries have to be processed online, i.e. to obtain each query, you need the answer to the previous query.

In each query, you are given a vertex v and a parameter k. For each vertex u in the subtree of v (including v), consider the value w_u $\oplus$ k ($\oplus$ denotes the bitwise XOR operation). The answer to this query is the maximum of these values and the smallest u such that vertex u is in the subtree of vertex v and w_u $\oplus$ k is equal to this maximum.

---

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and Q.
• The second line contains N space-separated integers w_1, w_2, ..., w_N.
• Each of the next N - 1 lines contains two space-separated integers x and y denoting that there is an edge between nodes x and y.
• The next Q lines describe queries. Each of these lines contains two space-separated integers a and b. The parameters v and k can be obtained in the following way: let's denote the value and vertex from the answer to the previous query by x_l and v_l respectively (x_l = v_l = 0 if this is the first query); then, v = a $\oplus$ v_l and k = b $\oplus$ x_l.

---

Output

For each query, print a single line containing two space-separated integers — the answer to the query, i.e. the number of the vertex for which we get the maximum value and the maximum value.

---

Constraints

• 1 <= T <= 1,000
• 1 <= N <= 2 * 10^5
• 1 <= Q <= 10^6
• 1 <= x, y, v <= N
• 1 <= w_i < 2^20 for each valid i
• 1 <= k < 2^20
• the sum of N over all test cases does not exceed 2 * 10^5
• the sum of Q over all test cases does not exceed 10^6

---

Subtasks

Subtask #1 (10 points):

• the sum of N over all test cases does not exceed 5,000
• the sum of Q over all test cases does not exceed 5,000

Subtask #2 (15 points):

• the sum of N over all test cases does not exceed 2,000
• the sum of Q over all test cases does not exceed 10^6

Subtask #3 (75 points): original constraints

---

Sample 1:

Input

1
10 5
9 17 93 16 3 61 23 11 2 1
1 2
2 5
5 8
1 3
1 4
3 6
3 7
6 9
6 10
4 14
7 123
5 103
9 32
5 118

Output

4 30
7 114
8 30
3 99
6 40

---

More Info

• Time limit: 2 secs