Fibonacci Terms up to M

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Print Fibonacci terms not exceeding M, starting F0=0, F1=1, and retaining both occurrences of 1. If M=0 print only 0.

Input

One integer M.

Output

Print all Fibonacci terms at most M separated by single spaces.

Subtasks

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

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

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

Examples

Example 1

Input:

5

Output:

0 1 1 2 3 5

Explanation: The printed sequence is 0,1,1,2,3,5.

Example 2

Input:

0

Output:

0

Explanation: Only zero meets the threshold.

Example 3

Input:

1

Output:

0 1 1

Explanation: Both occurrences of one are retained.