Permutation Construction with Prime Averages

Given a positive integer \(n\), construct a permutation \(p_1, p_2, \dots, p_n\) of the numbers from \(1\) to \(n\) such that the following condition holds:

For \(1 \le i \le n\), define \[ c_i = \left\lceil \frac{p_1 + p_2 + \cdots + p_i}{i} \right\rceil, \] where \(\lceil x \rceil\) denotes the ceiling function. Among the sequence \(c_1, c_2, \dots, c_n\), there must be at least \(\left\lfloor \frac{n}{3} \right\rfloor - 1\) prime numbers.

If there are multiple solutions, output any valid permutation.

inputFormat

The input consists of a single line containing a positive integer \(n\) (\(1 \le n \le 10^5\)).

outputFormat

Output a permutation of the integers from \(1\) to \(n\) as \(n\) space-separated integers such that the condition on the sequence \(c_i\) is satisfied.

sample

1

1