#include <bits/stdc++.h>

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define nmax 100005
int i,n,k,j,m,aib[100005];
#define mod 666013
struct cvv
{
    int st,dr,poz;
} a[nmax];
int x[nmax],last[nmax],sol[nmax];
void update(int poz, int val)
{
    int i;
    for(i=poz; i<=n; i+=i&(-i))
        aib[i]+=val;
}

int query(int poz)
{
    int i,s=0;
    for(i=poz; i>=1; i-=i&(-i))
        s+=aib[i];
    return s;
}
int comp(cvv a, cvv b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}
int main()
{
    fin>>n>>k>>m;
    for(i=1; i<=n; i++)
    {
        fin>>x[i];
        update(i,x[i]);
    }
    for(i=1; i<=m; i++)
    {
        fin>>a[i].st>>a[i].dr;
        a[i].poz=i;
    }
    sort(a+1,a+m+1,comp);
    i=1;
    for(j=1; j<=m; j++)
    {
        while(i<=a[j].dr)
        {
            if(last[x[i]])
            {
                update(last[x[i]],-x[i]);

            }
            last[x[i]]=i;
            i++;
        }
        sol[a[j].poz]=query(a[j].dr)-query(a[j].st-1);
    }
    for(j=1; j<=m; j++)fout<<sol[j]%mod<<'\n';

    return 0;
}