CSES - KILO 2018 2/5 - Lantern Line
  • Time limit: 1.00 s
  • Memory limit: 512 MB

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.