Cartofi

/*
2.3. Autor: Flavius Boian
*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("cartofi.in");
ofstream g("cartofi.out");

pair<int,int> fibo(long long n)
{
    if(n==0)
        return {0,1};
    auto p=fibo(n>>1ll);
    int ax=((p.second<<1)-p.first+10)%10;
    int c=(p.first*ax)%10;
    int d=(p.first*p.first+p.second*p.second)%10;
    if(n&1)
        return {d,(c+d)%10};
    return {c,d};
}

int n,m;
long long cols[61];
long long query(int);
void build();
void solve1();
void solve2();
void solve3();

int32_t main()
{
    int task;
    f>>task>>n>>m;
    if(task==1)
        solve1();
    else
        if(task==2)
            solve2();
        else
            solve3();
    return 0;
}

void solve1()
{
    long long ct=0,ax=(1ll*n*m)/60ll,ap=(1ll*n*m)%60ll;
    long long rez=0;
    for(int i=0,a=0,b=1,c;i<60;++i)
    {
        ct+=!b;
        if(i<ap)
            rez+=!b;
        c=(a+b)%10;
        a=b;
        b=c;
    }
    rez+=1ll*ax*ct;
    g<<rez;
}

void solve2()
{
    build();
    long long rez=0,ax;
    for(int i=n;i<=min(n+60,m);++i)
    {
        ax=query(i)-query(i-n);
        rez=max(rez,ax);
    }
    g<<rez;
}

void solve3()
{
    build();
    int q,st,dr;
    for(f>>q;q;--q)
    {
        f>>st>>dr;
        g<<(long long)query(dr)-query(st-1)<<'\n';
    }
}
void build()
{
    long long aux[61],prv=0,md=n%60,ct=n/60,ind;
    memset(aux,0,sizeof aux);
    for(int i=0,nr;i<min(n,60);++i,prv+=m)
        for(int j=1;j<=min(m,60);++j)
        {
            ind=prv;
            if(i&1)
                ind+=m-j+1;
            else
                ind+=j;
            nr=fibo(ind).first;
            cols[j]+=nr;
            if(i<md)
                aux[j]+=nr;
        }
    for(int i=1;i<=min(m,60);++i)
        cols[i]=1ll*cols[i]*ct+aux[i],cols[i]+=cols[i-1];
}

long long query(int poz)
{
    long long rez=1ll*(poz/60)*cols[60];
    rez+=cols[poz%60];
    return rez;
}