Fibonacci

Lab C++ Beginner 10 points

Read n (1–90) and print the first n Fibonacci numbers starting 0 1.

Input

One integer.

Output

One line.

Example

Input

Output

0 1 1 2 3 5 8 13 21 34

Sample input available Sample output available

Editor

C++

Hints

Keep the last two numbers.

Solution explanation

Two variables are all you need for the sequence.

Show solution

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        cout << a << (i < n - 1 ? " " : "\n");
        long long next = a + b;
        a = b;
        b = next;
    }
    return 0;
}

Output

Answer