#741 MEX with XOR

Statement

Statement language

You are given an integer array $B$ of length $N$ . Find an integer array $A$ of length $N$ satisfying the following conditions:

$0\le A_i<2^{30}$ ( $1\le i\le N$ ).

Here, $\oplus$ denotes bitwise XOR. The MEX of a collection is the smallest nonnegative integer absent from it. The MEX of an empty collection is $0$ .

If equal values occur more than once, remove only the occurrence at position $i$ when computing $M_i$ . Determine that it is impossible if no valid array exists.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the answer on one line.

If no valid array exists, print -1. Otherwise, print $A_1,A_2,\cdots,A_N$ , separated by spaces. If there are multiple solutions, print any of them.

Constraints

$1\le T\le10\,000$ .
$1\le N\le200\,000$ .
$0 \leq B_{}$ ().

Subtasks

#	Score	Constraints
1	6	$1\le B_i<2^{30}$ ( $1\le i\le N$ ).

Samples

Input

Output

In the first test case, removing the only element leaves an empty collection, so $M_1=0$ .

For the fourth test case, the output $A=(1,0,0)$ gives . Thus, .