Growth series

Problem

A growth model starts with 0 and 1, and every next value is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... (the Fibonacci series).

Given n, print the first n values on one line, separated by single spaces.

Input: One integer n.
Output: The first n values on one line, separated by single spaces, with no space at the end.
Constraints: 1 ≤ n ≤ 30

Example

Input

Output

0 1 1 2 3

Try the problem first. Open one hint at a time.

Hint 1

Keep two variables for the last two values. Print the first one, then move both forward.

Hint 2

Python can update both in one line: a, b = b, a + b.

Write your Python code, run it on the examples and submit it to hidden tests.