ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1744. Рота Капитана

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В роте n солдат. Каждый день три солдата должны вступить на ночное дежурство.
Капитан Очевидность уже начал составлять график дежурства для своей роты, но вдруг столкнулся с одним очевидным фактом. Любые два солдата, побывавшие вместе на одном из дежурств, начинают раздражать друг друга. Если два солдата уже дежурили вместе три раза, на четвёртый раз они могут разозлить друг друга настолько сильно, что, очевидно, произойдёт непоправимое.
Поэтому Капитан хочет составить график дежурства на как можно большее количество дней таким образом, чтобы любые два солдата дежурили вместе не более трёх раз. Капитану решение этой задачи далеко не очевидно, и он попросил вас помочь ему.

Исходные данные

В первой строке записано нечётное число n (3 ≤ n ≤ 99).

Результат

В первой строке выведите целое число k, максимальное количество дней, на которое можно составить график дежурств. В i-й из следующих k строк выведите через пробел номера трёх солдат, которые должны вступить на дежурство в i-й день. Солдаты занумерованы целыми числами от 1 до n.

Примеры

исходные данныерезультат
3
3
1 2 3
2 3 1
3 1 2
5
10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Автор задачи: Артём Рипатти
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009