#912 bbbbbbbbinary sequence

Statement

問題文の言語

長さ $m$ の二進文字列 $S=s_1s_2\cdots s_m$ と非負整数 $a$ に対し、 $S\ll a$ を次の無限二進数列として定義する。

(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}

先頭の文字がすべて $1$ である $N$ 個の二進文字列 $S_1,S_2,\ldots,S_N$ が与えられる。次を満たす非負整数が存在するか判定し、存在する場合はその一例を求めよ。

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

XOR は各位置で独立に計算し、右辺の $0$ はすべての項が $0$ である無限数列を表す。

$L=\max_{1\le i\le N}|S_i|$ 、 $B = (N - 2) (L$ とする。解が存在する場合、かつを満たす解も必ず存在する。出力する解はこの条件を満たさなければならない。

入力は次の形式で与えられる。

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

各テストケースについて 1 行出力せよ。解が存在しない場合は -1 を出力せよ。存在する場合は次の形式で $N$ 個の整数を出力せよ。

$a_1\ a_2\ \cdots\ a_N$

入力例

出力例

0 0
0 0 1
-1

1 番目のテストケースでは、2 つの文字列をシフトせずに重ねると、互いに打ち消し合います。

2 番目のテストケースでは、出力されたシフト量を適用すると、すべての位置で XOR が $0$ になります。

3 番目のテストケースでは、条件を満たすシフト量は存在しません。