#912 bbbbbbbbinary sequence

Statement

Statement language

Let $S=s_1s_2\cdots s_m$ be a binary string of length $m$ , and let $a$ be a nonnegative integer. Define $S\ll a$ as the following infinite binary sequence:

(S\ll a)_k= \begin{cases} 0 & (0\le k<a),\\ s_{k-a+1} & (a\le k<a+m),\\ 0 & (k\ge a+m). \end{cases}

You are given $N$ binary strings $S_1,S_2,\cdots,S_N$ . The first character of every string is .

Determine whether nonnegative integers $a_1,a_2,\cdots,a_N$ satisfying the following equation exist, and find one such sequence if it exists:

(S_1\ll a_1)\oplus(S_2\ll a_2)\oplus\cdots\oplus(S_N\ll a_N)=0.

The XOR is taken independently at every position, and the $0$ on the right-hand side denotes the infinite all-zero sequence.

Let $L=\max_{1\le i\le N}|S_i|$ and $B = (N - 2) (L$ . If a solution exists, there always exists one satisfying and . The printed solution must satisfy these conditions.

Input

The input is given from Standard Input in the following format:

$T$ case $_1$ case $_2$

Output

Print one line for each test case.

If no solution exists, print -1.

If a solution exists, print $N$ integers in the following format:

$a_1\ a_2\ \cdots\ a_N$

Constraints

$1\le T\le 16$ .
$2\le N\le 8$ .
$1\le |S_i|\le 2\,000$ ().

Samples

Input

Output

0 0
0 0 1
-1

In the first test case, the two strings cancel without any shift.

In the second test case, applying the printed shifts makes the XOR zero at every position.

The third test case has no valid shifts.