K. Факториалы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Натуральные числа – весьма интересный объект исследования, и математики постоянно подтверждают это, находя новые и новые интересные закономерности. Не менее интересными являются целочисленные функции от натуральных чисел, например – факториалы.

Очевидным является факт, что любое натуральное $$$ n $$$ можно представить как отношение двух факториалов: $$$$$$ n = \frac{n!}{(n - 1)!} .$$$$$$

Также широко известно, что некоторые целые числа можно представить в виде отношения одного факториала к произведению двух других, больших единицы: $$$$$$ n = \frac{a!}{b! \times c!} .$$$$$$

Примером таких чисел являются биномиальные коэффициенты: $$$$$$ C_n^k = \frac{n!}{k! (n-k)!} \quad = \gt \quad 6 = \frac{4!}{2! \times 2!}.$$$$$$

Ограничимся рассмотрением факториалов до $$$ 50\,000! $$$, и числами до $$$ 1\,000\,000\,000 $$$ . Напишите программу, которая по числу $$$ n $$$, определит, представимо ли оно в виде $$$$$$ n = \frac{a!}{b! \times c!}, $$$$$$ где $$$c \le b \lt a$$$.

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

Единственное целое число $$$ n $$$ ($$$ 1 \le n \le 10^9 $$$).

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

В единственной строке выведите три целых числа $$$ a $$$, $$$ b $$$ и $$$ c $$$ ($$$ 1 \lt c \le b \lt a \le 50\,000 $$$), разделенных пробелами. Если такое представление не единственное – выведите то, у которого числитель $$$ a $$$ наименьший, а если и таких решений несколько, то среди них выберите с меньшим числом $$$ b $$$. Если решения в пределах ограничений не существует – выведите три числа $$$ - 1$$$.

Примеры
Входные данные
5
Выходные данные
6 4 3
Входные данные
50000
Выходные данные
-1 -1 -1
Входные данные
1
Выходные данные
6 5 3
Входные данные
6
Выходные данные
4 2 2
Примечание

Жюри известно, что для любого числа $$$ n \gt 1 $$$ существует представление $$$ n = \frac{2n!}{((2n - 1)! \times 2! )} $$$ (и оно не единственное – подобных представлений вида $$$ n = \frac{(k! \times n)!}{(k! \times n - 1)! \times k!} $$$, при целом $$$ k \gt 1 $$$, бесконечно много). Для числа $$$ 50000 $$$ из второго примера ответ «-1 -1 -1» означает то, что его нельзя представить при ограничении $$$ a \le 50\,000 $$$.