#include<bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct numar
{
    int st,dr,poz;
} q[100005];
long long aib[100005],n,m,k,v[100005],sol[100005],ap[100005];
map<int , int>mp;

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

long long query(int p)
{
    long long sum=0;
    for(; p>0; p-=(p&-p))
        sum+=aib[p];
    return sum;
}

bool cmp(numar a, numar b)
{
    return a.dr<b.dr;
}

int main()
{
    fin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        fin>>v[i], mp[v[i]]=1;
    for(int i=1; i<=m; i++)
    {
        fin>>q[i].st>>q[i].dr;
        q[i].poz=i;
    }
    sort(q+1, q+1+m, cmp);
    int j=0;
    for(int i=1; i<=m; i++)
    {
        while(j<q[i].dr)
        {
            j++;
            if(ap[v[j]]==0)
                ap[v[j]]=j, update(j, v[j]);
            else if(ap[v[j]])
            {
                update(ap[v[j]], -v[j]);
                ap[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';

}