#include <iostream>
#include <vector>

class FibonacciGenerator {
private:
    static std::vector<long long> fib_table;
    
public:
    // O(1) lookup for Fibonacci numbers
    static long long getFibonacci(int index) {
        if (index < 0 || index >= fib_table.size()) {
            return -1; // Error case
        }
        return fib_table[index];
    }
    
    // Print Fibonacci number at given index
    static void printFibonacci(int index) {
        long long result = getFibonacci(index);
        if (result == -1) {
            std::cout << "Error: Index out of range" << std::endl;
        } else {
            std::cout << "Fibonacci number at index " << index << ": " << result << std::endl;
        }
    }
};

// Precomputed Fibonacci numbers (first 50)
std::vector<long long> FibonacciGenerator::fib_table = {
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
    89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
    10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
    1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155,
    165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
};

int main() {
    std::cout << "Fibonacci Number Generator (O(1) lookup)" << std::endl;
    std::cout << "========================================" << std::endl;
    
    // Test various indices
    int test_indices[] = {0, 5, 10, 15, 20, 25, 30, 40, 45, 49};
    int num_tests = sizeof(test_indices) / sizeof(test_indices[0]);
    
    for (int i = 0; i < num_tests; i++) {
        FibonacciGenerator::printFibonacci(test_indices[i]);
    }
    
    // Test error case
    std::cout << "\nTesting error case:" << std::endl;
    FibonacciGenerator::printFibonacci(50);
    
    return 0;
}