Problem description


Podziały liczb
(podzialy)
Memory limit: 32 MB
Time limit: 2.00 s

Napisz program, który: wczyta liczbę naturalną N, wyznaczy wszystkie jej podziały na sumę dowolnej liczby składników i wypisze je na standardowe wyjście w kolejności leksykograficznej.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

Twój program powinien wypisać wszystkie podziały liczby N w kolejności leksykograficznej. Każdy z nich powinien być wypisany w osobnym wierszu. Liczby podziału powinny być pooddzielane pojedynczymi odstępami i wypisane w kolejności niemalejącej.

Ograniczenia

1 ≤ N ≤ 50.

Przykład

Input Output
5
1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5