Fibonacci Sequence

Print first n Fibonacci numbers separated by spaces.

Your task

Write a complete program: read the input with input() and print the result with print().

Example

Input

10

Output

0 1 1 2 3 5 8 13 21 34