Дистанционный практикум по программированию

В холодильнике имеется N видов продуктов. Математик Василий решил приготовить несколько салатов так, чтобы выполнялись следующие два условия:

1.     Первый салат состоит из одного продукта, второй − из двух, третий − из трёх, и так далее.

2.     Каждый следующий салат, начиная со второго, должен содержать как минимум два новых продукта в сравнении с любым предыдущим.

Определите, какое максимальное количество салатов он сможет приготовить, а также какие продукты в них будут содержаться.

Например, при N=4 можно приготовить максимум три салата. Возможный вариант: первый салат включает только продукт 1, второй салат − продукты 2 и 4, третий салат − продукты 1, 2 и 3.

Входные данные

Входные данные содержат одно натуральное число N (1 ≤ N ≤ 30).

Выходные данные

В первой строке выходных данных выведите одно натуральное число M − максимальное количество салатов. В следующих M строках перечислите номера продуктов в каждом салате через пробел. В случае нескольких правильных ответов выведите любой.

 

Пример ввода 4 Пример вывода 3 1 2 4 1 2 3