Alice と Bob は「陸戦棋（Luzhanqi）」で遊んでいる。それぞれが以下の24個の駒からなる順列を持っている。
- 元帥（Field Marshal） 1個、階級 9
- 大将（General） 1個、階級 8
- 中将（Major General） 2個、階級 7
- 少将（Brigadier General） 2個、階級 6
- 大佐（Colonel） 2個、階級 5
- 少佐（Major） 2個、階級 4
- 大尉（Captain） 3個、階級 3
- 中尉（Lieutenant） 3個、階級 2
- 工兵（Engineer） 3個、階級 1
- 爆弾（Bomb） 2個
- 地雷（Landmine） 3個
勝者を決定するために、どちらかが勝利するか引き分けになるまで以下のプロセスを繰り返す。
- 両者の順列が空になった場合、ゲームは引き分けで終了する。
- Alice の順列が空になった場合、Bob の勝利となる。
- Bob の順列が空になった場合、Alice の勝利となる。
Alice の順列の先頭の駒を $A$、Bob の順列の先頭の駒を $B$ とする。$A$ と $B$ の戦闘の結果は以下の通りである。
$A$ と $B$ が同じ種類の駒である場合、または $A$ と $B$ のどちらかが爆弾である場合、両方とも取り除かれる。
- それ以外で、$A$ と $B$ のどちらかが地雷で、もう一方が工兵である場合、地雷が取り除かれ、工兵は生き残る。
- それ以外で、$A$ と $B$ のどちらかが地雷で、もう一方の階級が 1 より大きい場合、地雷は生き残り、もう一方は取り除かれる。
- それ以外の場合、 $A$ と $B$ の階級を比較し、階級が小さい方の駒が取り除かれる。
Bob は Alice の順列を事前に知っており、その情報に基づいて自身の順列を決定できる。Bob が自身の順列を決定した後、Alice は Bob の順列内の2つの駒を入れ替えることができる。Bob は、Alice がどの2つの駒を入れ替えたとしても Alice の順列に勝利できるような順列を構築できるか？
入力
最初の行にはテストケースの数 $T$ ($1 \le T \le 100$) が含まれる。 続く $T$ 行の各行には、Alice の順列を表す24個の整数が含まれる。
- 40 は元帥を表す
- 39 は大将を表す
- 38 は中将を表す
- 37 は少将を表す
- 36 は大佐を表す
- 35 は少佐を表す
- 34 は大尉を表す
- 33 は中尉を表す
- 32 は工兵を表す
- 31 は地雷を表す
- 30 は爆弾を表す
すべての順列は一様にランダムに選択され、問題文で説明された24個の駒を正確に含んでいることが保証される。
出力
各テストケースにつき1行で出力せよ。 Bob が条件を満たす順列を構築できない場合は -1 を出力せよ。 構築できる場合は、入力と同じ形式で Bob の順列を表す24個の整数を出力せよ。複数の解が存在する場合は、そのうちのどれを出力してもよい。Bob の順列は、問題文で説明された24個の駒を正確に含んでいなければならない。
入出力例
入力 1
4 40 39 38 38 37 37 36 36 35 35 34 34 34 33 33 33 32 32 32 31 31 31 30 30 34 31 36 33 31 39 37 38 35 32 32 35 36 31 34 32 38 40 30 33 30 34 33 37 37 30 40 38 36 38 32 34 36 35 37 32 34 33 31 30 33 31 35 34 33 39 31 32 30 33 32 39 37 38 35 40 34 30 31 37 31 33 31 33 34 32 36 36 35 34 32 38
出力 1
34 36 30 39 33 38 37 31 34 30 33 35 38 31 37 33 40 31 35 32 32 36 32 34 34 32 32 38 40 33 33 30 31 34 31 35 37 32 34 36 33 31 38 30 36 37 35 39 38 33 32 31 36 34 30 34 33 40 32 37 38 30 37 35 33 35 32 31 34 31 39 36 37 34 33 36 34 35 31 38 32 38 31 32 37 30 30 31 33 36 32 33 40 39 34 35