Square

Time Limit : 1 sec, Memory Limit : 65536 KB

同じ大きさの正方形の紙が n 枚ある.これらの紙の下部を水平に揃えて何列 かに並べる.ただし,隣り合う列は左側が右側より低くならないように並べなけれ ばならない.例えば, n = 5 のときは,次のような 7 通りの並べ方が可能である.



これらを,各列に並んだ正方形の個数の列で表すことにする.例えば, n = 5 の ときは,それぞれ,

          (5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)

と表わされる.

n を入力したとき, 辞書式順序で全て出力するプログラムを作成せよ.n ≤30 とする.ただし, 辞書式順序とは2つの並べ方 (a1, a2 , ..., as) が並べ方 (b1, b2, ..., bt ) に対して, a1 > b1 または, ある整数 i > 1 が存在して a1 = b1 , ..., ai-1 = bi-1 かつ ai > bi が成り立つとき (a1, a2, ..., as) が (b1 , b2, ..., bt) より先に出力されるように並べることである.

入力ファイルのファイル名は “input.txt” である.“input.txt” は 1 行からなり, 1 行目に n が書かれている.

出力ファイルのファイル名は “output.txt” である.“output.txt” には並べ方を 辞書式順序で 1 行に1通りずつ書き最後に改行を入れること. 並べ方は (a1, a2, ..., as) の出力は整数 a1, a2, . . . , as をこの順番に空白で区切って出力すること.

入力例

5

出力例

5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Notes on Submission

標準入出力を行うプログラムを作成して下さい。

上記の形式で複数のデータセットが与えられます。nが0のとき入力が終了します。

Sample Input

5
5
0

Sample Output

5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

Source: 5th Japanese Olympiad in Informatics , 2006-02-12
http://www.ioi-jp.org/