Bob loves absolutely even arrays. For an array $A$, let $X$ be the number of subarrays with a non-negative sum, and $Y$ be the number of subarrays with a negative sum. An absolutely even array of size $N$ is one which has the minimum absolute difference $|X-Y|$ over all possible arrays of size $N$. Please give Bob an example of an absolutely even array.

Constraints

$1\le N\le 2\times {10}^5$

Subtask 1 [30%]

$1\le N\le 8$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first and only line contains the integer $N$.

Output Specification

The first and only line of your output should contain $N$ space-separated integers $A_1,A_2,\dots ,A_N$, an array $A$ which minimizes the value of $|X-Y|$.

$\left|A_i\right|\le {10}^{12}$ must hold.

Sample Input

3

Sample Output

1 -3 2

Explanation for Sample

$X$ and $Y$ are both equal to $3$. The $3$ subarrays with a non-negative sum are $[1]$, $[1,-3,2]$, and $[2]$. The $3$ subarrays with a negative sum are $[1,-3]$, $[-3]$, and $[-3,2]$. The value of $|X-Y|$ is $0$, which is minimal.