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

const long long MOD=666013;

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

struct elem
{
    long long first,second,ind;
} w[100005];

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(long long poz,long long val)
{
    for(long long i=poz; i<=n; i+=i&-i)
    {
        aib[i]+=val;
    }
}

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

int main()
{
    fin>>n>>k>>q;
    for(long long i=1; i<=n; i++)
    {
        fin>>v[i];
        update(i,v[i]);
    }
    for(long long i=1; i<=q; i++)
    {
        fin>>w[i].first>>w[i].second;
        w[i].ind=i;
    }
    sort(w+1,w+q+1,cmp);
    long long val=1;
    for(long long 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);
    }
    for(long long i=1; i<=q; i++)
        fout<<ans[i]%MOD<<'\n';
    return 0;
}