XOR Subsequence

Alice used to have a sequence $a_1, \dots ,a_n$, but she has forgotten about it now. Fortunately, she noticed that she had calculated the $XOR$ sum for each non-empty subsequence of the sequence and obtained $2^n − 1$ results, but their order was disrupted.

Now she hopes you can help restore the sequence. If there are multiple possible sequences, please tell her the sequence with the smallest lexicographical order, or report there is no correct sequence.

Input

The first line contains a single integer $T \: (1 \leq T \leq 5000)$, denoting the number of test cases.

For each test case, the first line contains an integer $n \: (1 \leq n \leq 18)$.

The next line contains $2^n − 1$ non-negative integers strictly less than $2^{30}$, denoting the results.

It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{20}$.

Output

For each test case, output one line. If there is no correct sequence, output $−1$; otherwise, output $n$ integers denoting the answer.

Example

3
3
1 2 3 4 5 6 7
3
1 0 1 0 1 0 1
3
1 2 3 4 5 6 6

1 2 4
0 0 1
-1