#include <bits/stdc++.h>
using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

const int MOD=666013;

int n, val_max, q, st, dr, s_actual, st_actual, dr_actual, st_prev, dr_prev, s_prev;
int ultimstanga[100005];
int aparitiestanga[100005];

int ultimdreapta[100005];
int aparitiedreapta[100005];
int a[100005];
int rez[100005];
pair<pair<int,int>,int>query[100005];

void citire()
{
    f >> n >> val_max >> q;
    for (int i=1; i<=n; ++i)
    {
        f >> a[i];
        ultimdreapta[a[i]]=n+1;
        aparitiestanga[i]=ultimstanga[a[i]];
        ultimstanga[a[i]]=i;
    }
    for (int i=n; i>=1; --i)
    {
        aparitiedreapta[i]=ultimdreapta[a[i]];
        ultimdreapta[a[i]]=i;
    }
    for (int i=1; i<=q; ++i)
    {
        f >> query[i].first.first >> query[i].first.second;
        query[i].second=i;
    }
    sort(query+1,query+q+1);
}

void solve()
{
    int minstanga, maxdreapta;
    st_actual=query[1].first.first;
    dr_actual=query[1].first.second;
    for (int i=st_actual; i<=dr_actual; ++i)
    {
        if (aparitiestanga[i]<st_actual)
        {
            s_actual+=a[i];
            s_actual%=MOD;
        }
    }
    rez[query[1].second]=s_actual;
    for (int i=2; i<=q; ++i)
    {
        st_prev=st_actual;
        dr_prev=dr_actual;
        st_actual=query[i].first.first;
        dr_actual=query[i].first.second;

        if (dr_prev>st_actual && dr_prev<dr_actual)
        {
            for (int j=st_prev; j<st_actual; ++j)
            {
                if (aparitiedreapta[j]>dr_actual)
                {
                    s_actual-=a[j];
                    if (s_actual<0)
                        s_actual+=MOD;
                }
            }
            for (int j=dr_prev+1; j<=dr_actual; ++j)
            {
                if (aparitiestanga[j]<st_prev)
                {
                    s_actual+=a[j];
                    s_actual%=MOD;
                }
            }
        }

        else
        {
            s_actual=0;
            for (int j=st_actual; j<=dr_actual; ++j)
            {
                if (aparitiestanga[j]<st_actual)
                {
                    s_actual+=a[j];
                    s_actual%=MOD;
                }
            }
        }

        rez[query[i].second]=s_actual;

    }

    for (int i=1; i<=q; ++i)
        g << rez[i] <<'\n';
}

int main()
{
    citire();
    solve();
    return 0;
}