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

const long long MOD=666013;

long long aib[200005],v[200005],n,q,last[200005],ans[200005],k;

struct elem
{
    int first,second,ind;
} w[200005];

inline bool cmp(const elem a,const elem b)
{
    if(a.second==b.second)
        return a.first<b.first;
    return a.second<b.second;
}

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

int query(int poz)
{
    int sum=0;
    for(int i=poz; i>=1; i-=i&-i)
    {
        sum+=aib[i];
        sum%=MOD;
    }
    return sum;
}

int main()
{
    fin>>n>>k>>q;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        update(i,v[i]);
    }
    for(int i=1; i<=q; i++)
    {
        fin>>w[i].first>>w[i].second;
        w[i].ind=i;
    }
    sort(w+1,w+q+1,cmp);
    int val=1;
    for(int j=1; j<=q; j++)
    {
        while(val<=w[j].second)
        {
            if(last[v[val]]!=0)
                update(last[v[val]],-v[val]);
            last[v[val]]=val;
            val++;
        }
        ans[w[j].ind]=(query(w[j].second)-query(w[j].first-1)+MOD)%MOD;
    }
    for(int i=1; i<=q; i++)
        fout<<ans[i]<<'\n';
    return 0;
}