Natural numbers are a fascinating subject of study, and mathematicians constantly confirm this by discovering more and more interesting patterns. Equally interesting are integer functions of natural numbers, such as factorials.
It is obvious that any natural $$$n$$$ can be represented as the ratio of two factorials: $$$$$$ n = \frac{n!}{(n - 1)!} .$$$$$$
It is also well known that some integers can be represented as the ratio of one factorial to the product of two others greater than 1: $$$$$$ n = \frac{a!}{b! \times c!} .$$$$$$
An example of such numbers are the binomial coefficients: $$$$$$ C_n^k = \frac{n!}{k! (n-k)!} \quad = \gt \quad 6 = \frac{4!}{2! \times 2!}.$$$$$$
Let us limit ourselves to considering factorials up to $$$ 50\,000! $$$, and numbers up to $$$ 1\,000\,000\,000 $$$. Write a program that, given a number $$$n$$$ , determines whether it can be represented as $$$$$$ n = \frac{a!}{b! \times c!}, $$$$$$ where $$$c \le b \lt a$$$.
The input consists of a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$).
In a single line, print three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \lt c \le b \lt a \le 50\,000$$$), separated by spaces. If this representation is not the only one, print the one with the smallest numerator $$$ a $$$, and if there are several such solutions, then among them, select the one with the smallest number $$$ b $$$. If no solution exists within the constraints, print three numbers $$$-1$$$.
5
6 4 3
50000
-1 -1 -1
1
6 5 3
6
4 2 2
The jury knows that for any number $$$n \gt 1$$$ there exists a representation of the form $$$n = \frac{2n!}{((2n - 1)! \times 2! )} $$$ (and it's not the only one – there are infinitely many similar representations of the form $$$n = \frac{(k!\times n)!}{(k!\times n - 1)!\times k!}$$$, for a total of $$$k \gt 1$$$). For the number $$$50000$$$ from the second example, the solution "-1 -1 -1" means that it cannot be represented under the $$$a\le 50\,000$$$ constraint.
