1710 Magic of David Copperfield

原文

時間制限:1000ミリ秒
メモリ制限:10000KB
Special Judge

問題

有名なマジシャン、デビッド・カッパーフィールドが好むマジックがあった。それは以下のようなものである。

まず、テレビの画面に N 行 N 列のマス目が映される。このマス目には以下のように番号がつけられている。

まず最初に観客たちは左上のマス目(番号1)に指を置いて、そこからマジックが始められる。マジシャンは観客たちに、今居る所からk1回だけ指を動かすように言う(一回の動きでは上下左右の隣接するマス目にだけ移動できる)。そして観客が皆それぞれ指を動かし終わった後、マジシャンはちょいっと指を動かして幾つかのマス目を取り除き「あなたの指はここにはない！」と宣言する。……そして、それは正しい。確かに誰の観客の指も取り除かれたマス目にはない。次にマジシャンはk2回の移動をするように言う、そしてまた幾つかのマス目を消す。今度はk3回、k4回……と続く。そして最後、残りのマスが1つだけになってしまったとき、マジシャンは「つかまえた！」と宣言するのである(拍手喝采)。

そして今、デビッドはもう一度このマジックをやろうとしている。しかし残念なことに、ハードなスケジュールがたたってデビッドは頭痛に襲われてしまい、再現がとても難しくなってしまった。そしてあなたはデビッドを助けるために、このマジックを再現するようなプログラムを書かねばならない。

入力

入力は1つの整数 N (2 ≦ N ≦ 100)からなる。

出力

プログラムは次のようなフォーマットで何行か出力する。

k1 x[1,1] x[1,2] …… x[1,m1]
k2 x[2,1] x[2,2] …… x[2,m2]
 …………
ke x[e,1] x[e,2] …… x[e,me]

ここで ki は i番目に観客が指を動かす回数である (2N ≦ k ≦ 10000)。全ての ki は違っていなければならない(すなわち i ≠ j なら ki ≠ kj である)。x[i,1], x[i,2], ..., x[i,mi] はi番目にデビッドが取り除くいくつかのマス目の番号である(取り除くマス目の番号は任意でよい、ただし1つの番号は1回しか現れてはならないし、最低でも1つのマス目を毎回取り除かねばならない)。

1ターン分の動きはそれぞれ1行で表される。またそれぞれの数はスペース1個で区切られている必要がある。eターン分の動きが終わった後、1個を除いて全てのマス目が取り除かれていなければならない。

入力の例

3

出力の例

8 4 6
13 9
10 7 1
7 8
11 3 5

出典

Northeastern Europe 1997