Esoteric Bovines

Farmer Richard has a herd of $2 \cdot N$ mystical cows, meticulously divided between two barns. Every cow produces mystical milk which has a magic value between $1$ and $2^{60} − 1$, inclusive.

Unfortunately for Richard, his wife, Dara got sick and she requires a special type of magic milk to be cured. The magic milk is obtained by combining two kinds of mystical milk from two cows, one from the first barn and one from the second barn. The magic value of the combined milk is the bitwise xor of the magic values of the two kinds of milk.

In a rather bizarre turn of events, Richard had a dream where Șogard, the magical fairy responsible for the mystical properties of his cows, delivered a message. Șogard instructed Richard that if he wanted Dara to recover, she must consume the milk with the $K$-th smallest magic value out of all possible combinations of mystical milk.

In a hurry, Richard jumped from his bed and went to his barns, but unfortunately, his mystical cows had gone to the magic land to eat magic grass to regain their mystical strength. In his dizziness, he noted down $T$ possible scenarios, each consisting of the magic value $K$ given by Șogard, and two lists $A_0, A_1, \dots ,A_{N−1}$ and $B_0, B_1, \dots , B_{N−1}$, the magic values of milk produced by the cows in the first barn and in the second barn.

Being out of touch with programming since he embraced the tranquil life of farming, Richard turns to you for help in finding the answers to his $T$ scenarios.

Input

The first line contains the only integer $T$, the number of scenarios Richard wrote.

The first line of each scenario contains $N$ and $K$, the number of cows in each barn, and the position of the magic milk value he needs from the sorted list of all possible combinations.

The second line contains $N$ integers $A_0, A_1, \dots ,A_{N−1}$, denoting the magic values of the milk produced in the first barn.

The third line contains $N$ integers $B_0, B_1, \dots , B_{N−1}$, denoting the magic values of the milk produced in the second barn.

Output data

You need to write $T$ lines, each containing one integer: the $K$-th smallest magic value that can be obtained by mixing two kinds of milk, one from the first barn and one from the second barn.

Constraints and clarifications

• $1 \leq T \leq 10 \ 000$
• $1 \leq N \leq 200 \ 000$
• $1 \leq K \leq N^2$
• $1 \leq A_i < 2^{60} - 1$ for each $i = 0 \dots N − 1$.
• $1 \leq B_i < 2^{60} - 1$ for each $i = 0 \dots N − 1$.
• Additional constraint on the input: the sum of $N$ over all scenarios doesn’t exceed $200 \ 000$.

Examples

stdin

3
5 5
3 6 20 5 9
12 3 19 7 13
5 10
3 6 20 5 9
12 3 19 7 13
5 25
3 6 20 5 9
12 3 19 7 13

stdout

4
8
26

Explanation

In the sample case, the magic values in ascending order in each scenario are:

$0, 1, 2, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 11, 14, 14, 15, 16, 19, 21, 22, 23, 24, 25, 26$

So the fifth smallest magic value is $4$, the tenth is $8$ and the twenty fifth is $26$.