- 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.