Path XOR Rank - Repovive Premier Round 4 | Repovive

9G. Path XOR Rank

3500 pts4.7s512 MB

You are given a tree with $n$ vertices. Vertex $i$ has a value $a_i$ .

For every ordered pair of vertices $(u,v)$ with $1 \le u,v \le n$ , write down the xor of all values on the simple path from $u$ to $v$ .

There are exactly $n^2$ written numbers.

Find the $k$ -th smallest number among them.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n^2$
$0 \le a_i < 2^{30}$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given edges form a tree

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Explanation

Case 1

The written numbers are: $(1,1)$ : path $1$ , xor $5$ . After sorting, the first one is $5$ .

Case 2

The written numbers are: $(1,1)$ : path $1$ , xor $5$ . $(1,2)$ : path $1,2$ , xor $5 \oplus 3 = 6$ . $(2,1)$ : path $2,1$ , xor $3 \oplus 5 = 6$ . $(2,2)$ : path $2$ , xor $3$ . After sorting them as $3, 5, 6, 6$ , the third one is $6$ .

Case 3

The sorted written numbers are $1, 2, 3, 3, 4, 6, 6, 7, 7$ . The fifth one is $4$ .

Case 4

The sorted written numbers are $0, 0, 0, 1, 1, 1, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7$ . The seventh one is $6$ .

Case 5

The sorted written numbers are $0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7$ . The twelfth one is $3$ .

Output

You are given a tree with $n$ vertices. Vertex $i$ has a value $a_i$ .

For every ordered pair of vertices $(u,v)$ with $1 \le u,v \le n$ , write down the xor of all values on the simple path from $u$ to $v$ .

There are exactly $n^2$ written numbers.

Find the $k$ -th smallest number among them.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n^2$
$0 \le a_i < 2^{30}$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given edges form a tree

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The written numbers are: $(1,1)$ : path $1$ , xor $5$ . After sorting, the first one is $5$ .

The sorted written numbers are $1, 2, 3, 3, 4, 6, 6, 7, 7$ . The fifth one is $4$ .

The sorted written numbers are $0, 0, 0, 1, 1, 1, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7$ . The seventh one is $6$ .

The sorted written numbers are $0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7$ . The twelfth one is $3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9G. Path XOR Rank

Constraints

Input

Output

Samples

9G. Path XOR Rank

Constraints

Input

Output

Samples