#include <algorithm>
#include <iostream>

template<int N>
struct num
{
    char x[N + 1];

    num()
    {
        std::fill(x, x + N, '0');
        x[N] = '\0';
    }
};

template<int N>
num<N> operator+(num<N> a, const num<N>& b)
{
    int carry = 0;
    for (int i = N - 1; i >= 0; --i)
    {
        int sum = a.x[i] - '0' + b.x[i] + carry;
        if (sum <= '9')
        {
            a.x[i] = sum;
            carry = 0;
        }
        else
        {
            a.x[i] = sum - 10;
            carry = 1;
        }
    }
    return a;
}

template<int N>
num<N> fib(int n)
{
    num<N> a;
    num<N> b;
    b.x[N - 1] = '1';
    for (int i = 0; i < n; ++i)
    {
        std::cout << a.x << '\n';
        num<N> c = a + b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    std::cout << '\n' << fib<30>(100).x << '\n';
}