Задача 2. Разбиения на слагаемые

Автор:std.alg   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Перечислите все разбиения целого положительного числа N (1 ≤ N ≤ 40) на целые положительные слагаемые. Разбиения должны обладать следующими свойствами: 1. Слагаемые в разбиениях идут в невозрастающем порядке. 2. Разбиения перечисляются в лексикографическом порядке.

Формат входных данных

Первая строка входного файла содержит целое число N (1 ≤ N ≤ 40).

Формат выходных данных

Ограничения

Примеры тестов

Стандартный вход Стандартный выход
1
4
1 1 1 1
2 1 1
2 2
3 1
4

0.033s 0.008s 15