#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream ReadFromFile ("fibointerval.in");
    ofstream WriteToFile ("fibointerval.out");

    long long int N, Q, A, B, Suma = 0;

    // Q --> Numarul de linii
    ReadFromFile >> N >> Q;

    long long int Array[1001];

    Array[1] = 1;
    Array[2] = 1;

    // Q citiri
    for (int i=0; i<Q; i++)
    {
        ReadFromFile >> A >> B;

        if (A == 1)
            Suma = 2;

        if (A == 2)
            Suma = 1;

        if (A == 1 && B == 2)
        {
            WriteToFile << 1 << " " << 1 << " "  << 2 << "\n";
            continue;
        }

        for (int j=3; j<=B; j++)
        {
            Array[j] = Array[j-2] + Array[j-1];

            if (j >= A && j <= B)
                Suma += Array[j];

            if (j == A || j == B)
            {
                if (A == 1)
                    WriteToFile << 1 << " ";

                if (A == 2)
                    WriteToFile << 1 << " ";

                if (j == B)
                    WriteToFile << Array[j] << " " << Suma << "\n";
                else WriteToFile << Array[j] << " ";
            }
        }

        Suma = 0;
    }

    ReadFromFile.close();
    WriteToFile.close();
}