#include <bits/stdc++.h>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const int nmax=100005,MOD=666013;
pair<pair <int,int>,int> querys[nmax];
int n,k,m,a[nmax];
long long aib[nmax];
int st;
vector <int> valori[nmax];
void update(int p,int x)
{
    for (;p<=n;p+=(p&(-p)))
        aib[p]=aib[p]+x%MOD;
}
int query(int p)
{
    int s=0;
  //  cout<<"a";
    for (;p>0;p-=(p&(-p)))
        s=s+aib[p]%MOD;
    return s%MOD;
}
void advance(int T)
{int i,x;
    for (;st<T;st++)
    {
        x=a[st];
        valori[x][0]++;
         update(st,-x);
        if (valori[x][0]<valori[x].size())
        {
            update(valori[x][valori[x][0]],x);
        }
    }
}
int sol[nmax];
int main()
{
    in>>n>>k>>m;

    int i,q,w;
    for (i=1;i<=n;i++){in>>a[i];}
    for (i=1;i<=m;i++)
    {
        in>>q>>w;
        querys[i]={{q,w},i};
    }
    sort (querys+1,querys+1+m);
    st=querys[1].first.first;
    int x;
    for (i=st;i<=n;i++)
    {
        x=a[i];
        if (valori[x].empty()){update(i,x);valori[x].push_back(0);}
        else valori[x].push_back(i);
    }
    for (i=1;i<=m;i++)
    {
        if (st<querys[i].first.first)
        {
            advance(querys[i].first.first);
        }
       sol[querys[i].second]=query(querys[i].first.second);
    }
    for (i=1;i<=m;i++)out<<sol[i]<<"\n";
    out.close();
    in.close();
    return 0;
}