Dãy Fibonacci đến ngưỡng (Fibonacci Terms up to M)

Nguồn: Phước Hưng OJ

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

Đề bài

Liệt kê các số trong dãy Fibonacci không vượt quá M, bắt đầu F_0=0, F_1=1 và F_i=F_(i−1)+F_(i−2). Phải giữ cả hai số 1 liên tiếp (F_1 và F_2) khi M≥1. In theo đúng thứ tự dãy, kể cả giá trị trùng. Nếu M=0, chỉ in 0. Không in số đầu tiên vượt M.

Input

Một số nguyên M.

Output

Một dòng các số Fibonacci ≤M cách nhau một dấu cách, không có dấu cách cuối, có newline.

Subtask

• Subtask 1 (20%): 0 ≤ M ≤ 1000.

• Subtask 2 (30%): 0 ≤ M ≤ 10^9.

• Subtask 3 (50%): 0 ≤ M ≤ 10^15.

Ví dụ

Ví dụ 1

Input:

5

Output:

0 1 1 2 3 5

Giải thích: Có đủ hai số 1; số tiếp theo là 8 lớn hơn 5.

Ví dụ 2

Input:

0

Output:

0

Giải thích: 1 đã vượt ngưỡng 0.

Ví dụ 3

Input:

1

Output:

0 1 1

Giải thích: F1=F2=1 đều phải được in.