House Numbers

Interview

Time limit1sMemory limit512 MB

Summary

Given the first house number m, find the smallest n and the house x whose left and right neighbours' numbers sum equally.

Level: Medium5 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Peter was walking down the street and noticed that the houses on the street were numbered consecutively from $m$ to $n$ . Standing in front of a particular house $x$ , he also noticed that the sum of the house numbers behind him (numbered from $m$ to $x-1$ ) was equal to the sum of the house numbers in front of him (numbered from $x+1$ to $n$ ).

Given $m$ , and assuming there are at least three houses, find the smallest $n$ for which this is possible.

Input

The input consists of a single line containing the integer $m$ ( $1 \le m \le 1{,}000{,}000$ ).

Output

On a single line, print $m$ , $x$ , and $n$ , in that order, separated by spaces.

It is guaranteed that a solution exists with $n \le 10{,}000{,}000$ .

Examples4

Example 1
Input
```
1
```
Expected output
```
1 6 8
```
Example 2
Input
```
11
```
Expected output
```
11 49 68
```
Example 3
Input
```
999999
```
Expected output
```
999999 1317141 1571535
```
Example 4
Input
```
999000
```
Expected output
```
999000 1000000 1000999
```