집 번호

면접 대비

시간 제한1초메모리 제한512 MB

요약

첫 집 번호 m이 주어질 때, 왼쪽 집들과 오른쪽 집들의 번호 합이 같은 집 x와 그때의 최소 n을 찾습니다.

난이도: 보통10점 중 5점
유형: 수학, 정수론, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Peter는 길을 걷다가, 길에 있는 집들의 번호가 $m$ 부터 $n$ 까지 차례로 매겨져 있다는 것을 알았다. 그는 어떤 집 $x$ 앞에 서서, 자신의 뒤에 있는 집 번호의 합( $m$ 부터 $x-1$ 까지)과 앞에 있는 집 번호의 합( $x+1$ 부터 $n$ 까지)이 서로 같다는 것도 알았다.

$m$ 이 주어지고 집이 적어도 세 채 있다고 할 때, 이런 상황이 가능한 가장 작은 $n$ 을 구하라.

입력

입력은 정수 $m$ ( $1 \le m \le 1{,}000{,}000$ )을 포함하는 한 줄로 이루어진다.

출력

한 줄에 $m$ , $x$ , $n$ 을 순서대로 공백으로 구분하여 출력한다.

$n \le 10{,}000{,}000$ 인 해가 존재함이 보장된다.

예제4

예제 1
입력
```
1
```
예상 출력
```
1 6 8
```
예제 2
입력
```
11
```
예상 출력
```
11 49 68
```
예제 3
입력
```
999999
```
예상 출력
```
999999 1317141 1571535
```
예제 4
입력
```
999000
```
예상 출력
```
999000 1000000 1000999
```