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 ~\left | X-Y \right |~ 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 ~\left | X-Y \right |~.

~\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 ~\left | X-Y \right |~ is ~0~, which is minimal.