#include <bits/stdc++.h>

using namespace std;

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

const long long NMAX=100005;
const long long MOD = 666013;

vector<pair<pair<long long,long long>,long long>>intrebari;

long long n, k, m, ind_q=0,a , b;
long long sir[NMAX], aib[NMAX];
long long poz[NMAX];

void add(long long ind, long long val)
{
    for (;ind<=n;ind+=(ind&(-ind)))
    {
        aib[ind]+=val;
    }
}

long long query(long long ind)
{
    long long val=0;
    for (;ind>0; ind-=(ind&(-ind)))
        val+=aib[ind];
    return val;
}

long long rez[NMAX];

bool cmp(pair<pair<long long,long long>,long long>p1, pair<pair<long long,long long>,long long>p2)
{
    return p1.first.second<p2.first.second;
}

int main()
{
    f >> n >> k >> m;
    for (long long i=1; i<=n; ++i)
    {
        f >> sir[i];
    }
    pair<pair<long long,long long>,long long>p;
    for (long long i=0; i<m; ++i)
    {
        f >> p.first.first >> p.first.second;
        p.second=i;
        intrebari.push_back(p);
    }
    sort(intrebari.begin(),intrebari.end(), cmp);
    for (long long i=1; i<=n; ++i)
    {
        if (!poz[sir[i]])
        {
            poz[sir[i]]=i;
            add(i,sir[i]);
        }
        else
        {
            add(poz[sir[i]],-sir[i]);
            poz[sir[i]]=i;
            add(i,sir[i]);
        }
        while(ind_q<m && intrebari[ind_q].first.second==i)
        {
            a=query(intrebari[ind_q].first.second);
            b=query(intrebari[ind_q].first.first-1);
            rez[intrebari[ind_q].second]=a-b;
            ind_q++;
        }
    }
    for (long long i=0; i<m; ++i)
    {
        g << rez[i]%666013 <<'\n';
    }
    return 0;
}