There is a line of $n$ lanterns, numbered $1,2,\dots,n$. Initially, at time $0$, only lantern $1$ is on, and all others are off.

At time $t > 0$, the $i$'th lantern is on if exactly one of lanterns $i-1$ or $i-2$ was on at time $t-1$. There are two special cases: Lantern $1$ is never on at time $t > 0$, and lantern $2$ is on at time $t > 0$ if lantern $1$ is on at time $t - 1$.

For every time $t \in [0, n)$, find out how many lanterns are on.

Input

The first line of input contains a single integer $n$.

Output

Output $n$ integers $c_{0}, \dots, c_{n-1}$, where $c_{t}$ is the amount of lanterns on at time $t$.

Constraints

• $1 \leq n \leq 4 \cdot 10^{5}$

Example

Input:

6

Output:

1 2 2 3 1 1

Explanation:

0: 100000
1: 011000
2: 001010
3: 000111
4: 000010
5: 000001

Where the number on the left is the time $t$, and the $i$'th bit is 1 if lantern $i$ is on at time $t$, and 0 otherwise.