#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int nmax=1e5+5;
const int mod=666013;

int a[nmax],n,k,q,sum,bs;
int fr[nmax],ans[nmax];

struct qiqi
{
    int idx,st,dr;
};

vector <qiqi> query;

bool cmp (qiqi a, qiqi b)
{
    int bst=a.st/bs;
    int bdr=b.st/bs;

    if ( bst!=bdr ) return bst<bdr;
    return a.dr<b.dr;
}

void add(int pos)
{
    fr[a[pos]]++;
    if ( fr[a[pos]]==1 ) sum=(sum+a[pos])%mod;
}

void rem(int pos)
{
    fr[a[pos]]--;
    if ( fr[a[pos]]==0 ) sum=(sum-pos+mod)%mod;
}

signed main()
{
    f >> n >> k >> q;
    for (int i=1; i<=n; i++ )
        f >> a[i];

    for (int i=1; i<=q; i++ )
    {
        int x,y; f >> x >> y;
        query.push_back({i,x,y});
    }

    bs=max(1,(int)(sqrt(n)));
    sort(query.begin(),query.end(),cmp);

    int l=1, r=0;
    for (auto q:query )
    {
        int idx=q.idx;

        int st=q.st;
        int dr=q.dr;

        while ( l>st ) add(--l);
        while ( r<dr ) add(++r);
        while ( l<st ) rem(l++);
        while ( r>dr ) rem(r--);

        ans[idx]=sum;
    }

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