Codeforces 743C

Vladik and Chloe decided to determine who of them is better at math. Vladik claimed that for any positive integer (n) he can represent fraction (frac{2}{n}) as a sum of three distinct positive fractions in form (frac{1}{m}).

Help Vladik with that, i.e for a given (n) find three distinct positive integers (x, y) and (z) such that (frac{2}{n} = frac{1}{x} + frac{1}{y} + frac{1}{z}). Because Chloe can't check Vladik's answer if the numbers are large, he asks you to print numbers not exceeding (10^9).

If there is no such answer, print (-1).

Input

The single line contains single integer (n (1 le n le 10^4)).

Output

If the answer exists, print 3 distinct numbers (x, y) and (z (1 le x, y, z le 10^9, x eq y, x eq z, y eq z)). Otherwise print (-1).

If there are multiple answers, print any of them.

Examples

input
3
output
2 7 42
input
7
output
7 8 56

Solution

题意

给定一个正整数 (n)，求正整数 (x,y,z) 满足 (frac{2}{n} = frac{1}{x} + frac{1}{y} + frac{1}{z})。

其中 (x eq y, x eq z, y eq z)。若无解输出 (-1)。

题解

构造

[frac{1}{n} - frac{1}{n + 1} = frac{1}{n(n+1)} ]

[frac{1}{n} = frac{1}{n + 1} + frac{1}{n(n+1)} ]

[frac{2}{n} = frac{1}{n + 1} + frac{1}{n(n+1)} + frac{1}{n} ]

当 (n=1) 时，(frac{2}{n}=2)。而 ((frac{1}{x}+frac{1}{y}+frac{1}{z})_{max} = frac{1}{1}+frac{1}{2}+frac{1}{3} < 2)，所以当 (n=1) 时无解。

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if(n == 1) cout << -1 << endl;
    else cout << (n + 1) << " " << (n * (n + 1)) << " " << n << endl;
    return 0;
}