Chat in Telegram

Fibonacci

EASY

Fibonacci numbers are a sequence of numbers in which the first two numbers are 0 and 1, and each subsequent number is equal to the sum of the two previous numbers.
You should to write code that prints the first n numbers of this sequence.

INPUT:
n - count of numbers to print

OUTPUT:
a sequence of numbers separated by spaces

Example #1

Input

6

Output

0 1 1 2 3 5

Example #2

Input

4

Output

0 1 1 2

Solution