Easy Fibonacci

Nguồn: beecrowd

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n$. In đúng $n$ số đầu tiên của dãy Fibonacci, bắt đầu $F_0=0,F_1=1$ và $F_t=F_{t-1}+F_{t-2}$ với $t\ge2$. Các số cách nhau đúng một dấu cách, không có dấu cách cuối dòng.

Input

Một dòng chứa số nguyên $n$.

Output

Một dòng gồm đúng $n$ số.

Subtask

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

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

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

Ví dụ

Ví dụ 1

Input:

5

Output:

0 1 1 2 3

Giải thích:

Bắt đầu từ 0,1, mỗi số sau bằng tổng hai số trước; in đúng 5 số trong dòng.

Ví dụ 2

Input:

1

Output:

0

Giải thích:

Bắt đầu từ 0,1, mỗi số sau bằng tổng hai số trước; in đúng 1 số trong dòng.