Fibonacci Series

The Fibonacci series starts with 0 and 1, and every later term is the sum of the two before it: 0 1 1 2 3 5 8 13 ...

Given N, print the first N terms on a single line, separated by single spaces.

When N is 1 the output is just 0. When N is 2 it is 0 1.

💡

Keep two variables for the previous two terms and update them as you loop. You do not need an array, and you certainly do not need recursion here.

Input

A single line containing one integer N.

Output

The first N Fibonacci terms on one line, separated by spaces.

Constraints

1 <= N <= 50

Example 1

Input

Output

0 1 1 2 3

Each term after the first two is the sum of the previous two.

Submit runs your code against 5 test cases — the 1 shown above plus 4 hidden ones covering the awkward cases. Run sample just tries the first example, which is usually what you want while you are still working it out.