Задача 80. Сон скупого ≡

Условие

Скупец, одиножды на сундуках сидевши

И на замки глядевши,

Зевал  — зевал,

Потом и задремал.

Заснул  — как вдруг ему такой приснился сон,

Что будто нищему копейку подал он.

Со трепетом схватился  —

Раз пять перекрестился  —

И твёрдо поклялся уж никогда не спать,

Чтоб снов ему таких ужасных не видать.

Николай Гнедич, "Сон скупого", 1805 г.

Но на следующую ночь скупцу приснился ещё более страшный сон — как будто все свои деньги, бережно сложенные в три сундука (в первом a копеечных монеток, во втором b пятикопеечных, в третьем с десятикопеечных) раздаёт он нищим. Не хочет — а раздаёт, трясётся — а раздаёт, плачет — а всё равно раздаёт! Так всё и раздал.

И смотрит он на свои опустевшие сундуки, и пытается вспомнить, сколько же монет лежало в каждом. Я не буду просить вас назвать точное число различных подходящих наборов a, b и с — это число будет слишком большим. Найдите только такие наборы, в которых числа a, b и с образуют неубывающую геометрическую прогрессию.

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

Единственная строка входного файла содержит натуральное число n — общая сумма денег скупца в копейках.

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

В первой строке выведите одно неотрицательное целое число k — количество различных подходящих наборов. В следующих k строках через пробел выведите три натуральных числа a, b и с. Наборы упорядочите по возрастанию a.

Ограничения

16 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 1000, получат не менее 30 баллов.

Пояснение к примерам

В первом примере подходящих наборов нет.

Во втором примере подходящих наборов два. Проверим их:

3 × 1 + 18 × 5 + 108 × 10 = 1173 и 3, 18, 108 — геометрическая прогрессия (знаменатель 6).

23 × 1 + 46 × 5 + 92 × 10 = 1173 и 23, 46, 92 — геометрическая прогрессия (знаменатель 2).

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

17

0

1173

2
3 18 108
23 46 92