Nils, Canada's most popular interior designer, has been tasked with selecting aesthetically pleasing potted plants!

There are $K$ species of plants, labelled between $1$ and $K$, where plants of the same species look identical. Nils has been asked to form a straight line of $N$ pots, where each pot contains one of the $K$ types of plants, subject to the following constraints:

• The display of plants is symmetrical, that is, the sequence of plants is palindromic.
• For visual appeal, no two different contiguous sections of pots should contain identical sequences of plants, with both sequences containing more than one plant. Formally, every contiguous subsequence of the plants with a length greater than $1$ should be unique.

Nils will be paid more for selecting a greater number of plants, so he wishes to maximise the value of $N$.

Can you help him find an optimal selection of plants?

Constraints

$1\le K\le 2000$

Subtask 1 [40%]

$K$ is prime.

Subtask 2 [60%]

No additional constraints.

Input Specification

The only line contains a single integer, $K$.

Output Specification

Output $N$ space-separated integers, corresponding to the sequence of selected plants. Any valid sequence which maximises $N$ will be accepted.

Sample Input

2

Sample Output

1 2 2 1

Explanation

This sequence has $N=4$, is palindromic, and satisfies the condition that every contiguous subsequence with a length greater than $1$ is unique. It can be shown that this is the largest possible value of $N$.