Easy Fibonacci

Source: beecrowd

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$, output exactly the first $n$ Fibonacci numbers with $F_0=0$, $F_1=1$ and $F_t=F_{t-1}+F_{t-2}$ for $t\ge2$. Separate numbers with one space, without a trailing space.

Input

One line contains integer $n$.

Output

One line of exactly $n$ integers.

Subtasks

• Subtask 1 (20%): $1\le n\le 8$.

• Subtask 2 (30%): $1\le n\le 25$.

• Subtask 3 (50%): $1\le n\le 46$.

Examples

Example 1

Input:

5

Output:

0 1 1 2 3

Explanation:

Start with 0 and 1; each next number is the sum of the previous two. Print exactly 5 values.

Example 2

Input:

1

Output:

0

Explanation:

Start with 0 and 1; each next number is the sum of the previous two. Print exactly 1 values.