CODE FESTIVAL 2016 Final (Parallel)

B - Exactly N points


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 300

問題文

ある年のCODE FESTIVALの決勝では N 問の問題が出題されました。

i (1≦i≦N) 番目の問題の配点は i 点です。

高橋くんは、このコンテストでちょうど N 点を取りたいと思い、そのために解く問題の集合をどうするかを考えています。

配点が高い問題は難しいので、解く問題の配点のうちの最大値が最小になるようにしようと考えました。

高橋くんが解くべき問題の集合を求めてください。

制約

  • 1≦N≦10^7

部分点

  • 1≦N≦1000 を満たすデータセットに正解した場合は、200 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 100 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

点数の合計がちょうど N となるような集合のうち、配点の最大値が最小となるようなものを求め、その集合に含まれる問題の番号を 1 行にひとつずつ出力せよ。昇順に出力する必要はありません。

そのような集合が複数考えられる場合は、いずれを出力しても構わない。


入力例 1

4

出力例 1

1
3

4 番目の問題のみを解いた場合もちょうど 4 点が得られますが、1,3 番目の問題を解く方が配点の最大値が小さくなります。


入力例 2

7

出力例 2

1
2
4

\{3,4\} という集合も考えられます。


入力例 3

1

出力例 3

1

Score : 300 points

Problem Statement

The problem set at CODE FESTIVAL 20XX Finals consists of N problems.

The score allocated to the i-th (1≦i≦N) problem is i points.

Takahashi, a contestant, is trying to score exactly N points. For that, he is deciding which problems to solve.

As problems with higher scores are harder, he wants to minimize the highest score of a problem among the ones solved by him.

Determine the set of problems that should be solved.

Constraints

  • 1≦N≦10^7

Partial Score

  • 200 points will be awarded for passing the test set satisfying 1≦N≦1000.
  • Additional 100 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N

Output

Among the sets of problems with the total score of N, find a set in which the highest score of a problem is minimum, then print the indices of the problems in the set in any order, one per line.

If there exists more than one such set, any of them will be accepted.


Sample Input 1

4

Sample Output 1

1
3

Solving only the 4-th problem will also result in the total score of 4 points, but solving the 1-st and 3-rd problems will lower the highest score of a solved problem.


Sample Input 2

7

Sample Output 2

1
2
4

The set \{3,4\} will also be accepted.


Sample Input 3

1

Sample Output 3

1

Submit提出する