J問題 - Hyper Tsuru Puzzle(easy)

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

\(N\)次元空間の座標\((0,0,\cdots,0)\)~\((2,2,\cdots,2)\)(合計\(3^N\)個の格子点)に1枚ずつ鶴の剣のブロマイドが置かれています。

\(3^N\)枚の鶴の剣のブロマイドのうち、\(M\)枚が白色で、\(k\)枚目の鶴の剣のブロマイドは座標\((A_{k,1}, A_{k,2},\cdots,A_{k,N})\)に置かれています。 それ以外の\(3^N - M\)枚の鶴の剣のブロマイドは黒色です。

ここである操作を座標\((0,0,\cdots,0)\)~\((2,2,\cdots,2)\)のそれぞれに対して行うことが出来ます。(行わなくてもよい)

操作

• 選んだ座標に接する(そこからマンハッタン距離が1以下である)座標におかれている鶴の剣のブロマイドの色を反転(白色は黒色に、黒色は白色に)させる。

すべての鶴の剣のブロマイドを黒色にするために必要な操作の回数\(S\)と操作を行う座標\((B_{k,1}, B_{k,2},\cdots,B_{k,N})\)を辞書順に出力してください。

また条件を満たす操作を行う座標の組がない場合、-1と一行で出力してください。

制約

• \(0 \leq N \leq 4\)
• \(0 \leq M \leq 3^N\)
• \(0 \leq A_{k,i} \leq 2 \quad (1 \leq i \leq N, \: 1 \leq k \leq M)\)
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

N M
A_1,1 A_1,2 ... A_1,N
A_2,1 A_2,2 ... A_2,N
...
A_M,1 A_M,2 ... A_M,N

出力

標準出力に，次の形式で出力してください。

S
B_1,1 B_1,2 ... B_1,N
B_2,1 B_2,2 ... B_2,N
...
B_S,1 B_S,2 ... B_S,N

入力例1

2 6
0 0
0 1
0 2
2 0
2 1
2 2

出力例1

2
0 1
2 1

入力例2

3 27
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

出力例2

13
0 0 1
0 1 0
0 1 2
0 2 1
1 0 0
1 0 2
1 1 1
1 2 0
1 2 2
2 0 1
2 1 0
2 1 2
2 2 1

入力は最大で\(3^N\)行与えられます。

入力例3

4 0

出力例3

0

\(M\)が0のとき、それはすでに全てのブロマイドが通常であるということです。

入力例4

0 1

出力例4

1

\(N\)が0のとき、\(A_k\)は要素を持たないことに注意してください。

入力は0 1の後に2回改行が入っています。

また、出力には1の後に2回改行を入れる必要があることに注意してください。