First n Fibonacci terms

Problem

The Fibonacci series starts 0, 1, and each next term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... Read n and print the first n terms.

Input: One integer n.
Output: The first n terms on one line, separated by single spaces.
Constraints: 1 ≤ n ≤ 92
The 92nd term is the last one that fits in a long.

Example

Input

Output

0 1 1 2 3 5 8 13

0 1 1 2 3 5 8 13.

Try the problem first. Open one hint at a time.

Hint 1

Keep only the last two terms in two variables, a and b.

Hint 2

Each round print a, then move forward: the new a is b, and the new b is a + b. Use a third variable for the sum.

Write your Java code, run it on the examples and submit it to hidden tests.