ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1595. Perfect Sequence

Time limit: 1.0 second
Memory limit: 64 MB
Let’s call the sequence of positive integers N-perfect, if the following conditions are satisfied:
  • the sequence contains all the numbers 1, 2, …, N;
  • its length does not exceed 2N;
  • all the numbers in the sequence are different;
  • the sum of any of its first k members is divisible by k.
For example, the sequence 1, 3, 2, 6, 8 is 3-perfect.

Input

The only line contains integer N (1 ≤ N ≤ 250000).

Output

Output N-perfect sequence in a single line. Its members must not exceed 1013. Separate numbers with spaces. At least one such sequence always exists. If several answers are possible, output any one of them.

Sample

inputoutput
3
1 3 2 6 8
Problem Author: Aleksandr Bacherikov