//-----------------------------------------------------------------------------

#include <mutex>
#include <vector>

//-----------------------------------------------------------------------------

namespace fibonacci
{
    template<class T> class limits // f(x) = y
    {
    };

    template<> class limits<int8_t>
    {
    public:
        static constexpr int8_t x = 11;
        static constexpr int8_t y = 89;
    };

    template<> class limits<uint8_t>
    {
    public:
        static constexpr uint8_t x = 13;
        static constexpr uint8_t y = 233;
    };

    template<> class limits<int16_t>
    {
    public:
        static constexpr int16_t x = 23;
        static constexpr int16_t y = 28657;
    };

    template<> class limits<uint16_t>
    {
    public:
        static constexpr uint16_t x = 24;
        static constexpr uint16_t y = 46368;
    };

    template<> class limits<int32_t>
    {
    public:
        static constexpr int32_t x = 46;
        static constexpr int32_t y = 1836311903;
    };

    template<> class limits<uint32_t>
    {
    public:
        static constexpr uint32_t x = 47;
        static constexpr uint32_t y = 2971215073;
    };

    template<> class limits<int64_t>
    {
    public:
        static constexpr int64_t x = 92;
        static constexpr int64_t y = 7540113804746346429ull;
    };

    template<> class limits<uint64_t>
    {
    public:
        static constexpr uint64_t x = 93;
        static constexpr uint64_t y = 12200160415121876738ull;
    };

}; // namespace fibonacci

//-----------------------------------------------------------------------------

template<typename T> constexpr T fib1(T n)
{
    if (n < 2)
        return n;
    else
        return fib1(n - 2) + fib1(n - 1);
}

//-----------------------------------------------------------------------------

template<typename T> constexpr T fib2(T n)
{
    T i = 1, j = 0;
    for (T k = 0; k < n; ++k)
    {
        T t = i + j;
        i = j;
        j = t;
    }
    return j;
}

//-----------------------------------------------------------------------------

template<class T> constexpr T fib3(T n)
{
    if (n < 2)
        return n;

    T t1 = 0, t2 = 1, a = t2, b = t1, c = t1, d = t2;
    for (T i = n - 1; i > 0; i >>= 1)
    {
        if ((i & 1) != 0)
        {
            t1 = a * c + b * d;
            t2 = (a + b) * d + b * c;
            a = t1;
            b = t2;
        }
        t1 = c * c + d * d;
        t2 = (2 * c + d) * d;
        c = t1;
        d = t2;
    }
    return a + b;
}

//-----------------------------------------------------------------------------

template<class T> constexpr T fib4(T n)
{
    static std::vector<T> solutions = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};

    try
    {
        return solutions.at(n);
    }
    catch (...)
    {
        std::size_t size = solutions.size();
        solutions.resize(n + 1);
        for (auto i = solutions.begin() + size; i != solutions.end(); ++i)
            *i = *(i - 2) + *(i - 1);
    }

    return solutions[n];
}

//-----------------------------------------------------------------------------

template<class T> constexpr T fib5(T n)
{
    static std::vector<T> solutions = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
    std::size_t size = solutions.size();

    if (n >= size)
    {
        solutions.resize(n + 1);
        for (auto i = solutions.begin() + size; i != solutions.end(); ++i)
            *i = *(i - 2) + *(i - 1);
    }

    return solutions[n];
}

//-----------------------------------------------------------------------------

template<class T> constexpr T fib6(T n)
{
    static std::once_flag flag;
    std::call_once(flag, [&] { fib5(fibonacci::limits<T>::x); });

    return fib5(n);
}

//-----------------------------------------------------------------------------