ソーシャルネットワークでニュースを追っているなら、ワクチンで人々にチップを埋め込んだり、フッ素で体液を汚染したりする計画を持つさまざまな秘密組織について、いくつもの陰謀論を聞いたことがあるだろう。若い Martin は最近、まさにそのような組織の一つから、有名なクロアチアの新聞の社長の仕事を与えられた。

組織が新聞に興味を持ったのには理由がある。すべての構成員にゆっくりと非効率的にメッセージを送り、同時にできるだけ多くの陰謀論を生み出す方法が必要なのだ。ある数秘術的な性質のため、組織は Martin に、メッセージを送るために変わった媒体を使うよう命じた。記事の文章にメッセージを隠す代わりに、新聞のパズル欄に隠さなければならない。具体的には、数独パズルに隠すのである。

数独パズルは $9 \times 9$ のマスからなる行列で、一部のマスに一から九までの数字が入っている。パズルは 9 行、9 列、そして大きさ $3 \times 3$ の正方形のブロック 9 個に分かれている。すべてのマスが一から九までの数字で埋められ、どの行、列、ブロックでも数字が重複しないとき、パズルは解かれたとみなされる。

Martin の仕事は、$N$ 個の単語 $s_i$ を $N$ 個の数独パズルに符号化し、そのパズルを再び単語へ復号するプログラムを書くことである。

新聞のパズル担当者は、Martin がどんな数独パズルでも新聞に載せることを許すわけではない。Martin が提案した完成済みのパズルから、必要な難易度に応じていくつかの数字を取り除いてパズルを作る。したがって、Martin のプログラムは単語を完成済みの数独パズルに符号化しなければならない。

Martin の上司たちは、組織のすべての構成員がこのようなパズルを解けるはずだと考えているので、プログラムの復号部分も、すべてのマスが埋まったパズルだけを復号すればよい。

Martin はプログラミングが得意ではないので、あなたにそのようなプログラムを書いてほしいと頼んでいる。

入力

最初の行に自然数 $M$、$N$ が与えられる ($M=1$ または $M=2$、$1 \le N \le 30$)。$M=1$ の場合、プログラムは $N$ 個の文字列を数独パズルに符号化しなければならない。$M=2$ の場合、プログラムは $N$ 個の数独パズルを文字列へ復号しなければならない。

$M=1$ の場合、続く $N$ 行のうち $i$ 行目に自然数 $l_i$ と文字列 $s_i$ が一つずつ与えられる ($1 \le |s_i| = l_i \le 15$)。文字列 $s_i$ は英小文字だけからなる。

$M=2$ の場合、続く $9N$ 行に、復号する数独パズルを表す $N$ 個の $9 \times 9$ 行列が与えられる。行列は常に正しいパズルを構成する。つまり、文字 1 から 9 で構成され、$3 \times 3$ のブロック、行、列のどこでも同じ数字が重複しない。

出力

$M=1$ の場合、入力の文字列 $s_i$ を符号化した値を表す $N$ 個の数独パズルを $9N$ 行に出力せよ。出力するパズルは文字 1 から 9 だけで構成され、行、列、$3 \times 3$ のブロックの中で数字が重複してはならない。

$M=2$ の場合、入力の数独パズルを復号した文字列を $N$ 行に出力せよ。

小課題

あなたのプログラムは二段階でテストされる。まず、$M=1$ の公式入力データで実行される。プログラムの出力が $N$ 個の正しい行列の列であれば、第二段階では第一段階で出力された行列を入力として、プログラムが再び実行される。第二段階でプログラムが出力する文字列が公式入力データの文字列と等しければ、その公式入力について満点を得る。

プログラムの実行時間は、評価の両段階の実行時間の合計である。

入出力例

入力 1

1 1
6 sudoku

出力 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

入力 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

出力 2

sudoku