#include <bits/stdc++.h>
#define nmax 100005
#define ll long long
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
struct cv
{
    int st,dr,poz;
} q[nmax];
ll n,k,m,v[nmax],aib[nmax],aparitie[nmax],sol[nmax];
void update(int p,int val)
{
    for(; p<=n; p+=(p&-p))
        aib[p]+=val;
}
ll query(int p)
{
    ll sum=0;
    for(; p>0; p-=(p&-p))
        sum+=aib[p];
    return sum;
}
bool cmp(cv a, cv b)
{
    return a.dr<b.dr;
}
int main()
{
    fin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    for(int i=1; i<=m; i++)
    {
        fin>>q[i].st>>q[i].dr;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    int j=0;
    for(int i=1; i<=m; i++)
    {
        while(j<q[i].dr)
        {
            j++;
            if(aparitie[v[j]])
                update(aparitie[v[j]],-v[j]);
            aparitie[v[j]]=j;
            update(j,v[j]);
        }
        sol[q[i].poz]=(query(q[i].dr)-query(q[i].st-1)+mod)%mod;
    }
    for(int i=1; i<=m; i++)
        fout<<sol[i]<<'\n';
    return 0;
}