#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=100005;
const int MOD = 666013;

vector<pair<pair<int,int>,int>>intrebari;

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

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

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

int rez[NMAX];

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

int main()
{
    f >> n >> k >> m;
    for (int i=1; i<=n; ++i)
    {
        f >> sir[i];
    }
    pair<pair<int,int>,int>p;
    for (int 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 (int i=1; i<=n && ind_q<m; ++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 (int i=0; i<m; ++i)
    {
        g << rez[i]%666013 <<'\n';
    }
    return 0;
}