Chef is given a tree with N nodes and a positive integer K. Each node is assigned a value A_{i}.

Chef has to divide the tree into a forest of exactly K trees, numbered from 1 to K, such that each node belongs to exactly one tree.
Let B_{i} denote the [bitwise XOR] of the values of all nodes belonging to the i^{th} tree.

Find the maximum possible value of B_{1} \& B_{2} \& $\dots$ \& B_{K}, where \& denotes the [bitwise AND operation].

------ Input Format ------

• The first line contains a single integer T, the number of test cases.
• Each test case consists of multiple lines:
• The first line contains two space-separated integers N and K — the number of nodes in the tree and a positive integer as mentioned in the statement, respectively.
• The next line contains $N space-separated integers A_{1},A_{2},\ldots,A_{N}$, the values assigned to each node.
• The next (N-1) lines describe the edges. The i^{th} of these (N-1) lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between nodes u_{i} and v_{i}.

------ Output Format ------

For each test case, print a single integer, the maximum possible value of B_{1} \& B_{2} \& $\dots$ \& B_{K}

------ Constraints ------

$1 ≤ T ≤ 5 \cdot 10^{4}$
$1 ≤ K ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
$1 ≤u_{i}, v_{i} ≤N$, $(u_{i}\neq v_{i})$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
2
6 2
1 4 2 2 1 5
1 2
1 3
2 4
2 5
3 6
8 3
1 13 5 14 2 9 0 8
1 2
1 3
1 4
2 5
3 6
3 7
6 8
----- Sample Output 1 ------
6
4
----- explanation 1 ------
Test case $1$: A possible way of dividing the nodes into $2$ trees is $[1,3,6]$ and $[2,4,5]$.
- $B_{1} = A_{1}\oplus A_{3}\oplus A_{6} = 1\oplus 2\oplus 5 = 6$
- $B_{2} = A_{2}\oplus A_{4}\oplus A_{5} = 4\oplus 2\oplus 1 = 7$

Thus, $B_{1}$ $\&$ $B_{2} = 6$ $\&$ $7 = 6$.
Note that this is the maximum possible value of $B_{1}$ $\&$ $B_{2}$ you can obtain.
Another way of dividing is $[1,2,4,5]$ and $[3,6]$, which leads to the same answer.

Test case $2$: A possible way of dividing the nodes into $3$ trees is $[1,3,6,7,8]$, $[4]$, and $[2,5]$
- $B_{1} = A_{1}\oplus A_{3}\oplus A_{6}\oplus A_{7}\oplus A_{8} = 1\oplus 5\oplus 9 \oplus 0\oplus 8 = 5$
- $B_{2} = A_{4} = 14$
- $B_{3} = A_{2}\oplus A_{5} = 13\oplus 2 = 15$.

Thus, $B_{1}$ $\&$ $B_{2}$ $\&$ $B_{3} = 5$ $\&$ $14$ $\&$ $\&$ $15 = 4$.
Note that this is the maximum possible value of $B_{1}$ $\&$ $B_{2}$ $\&$ $B_{3}$ you can obtain.

见题面

见题面