#include<bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
struct elem
{
    long long st,dr,index;
};
elem w[100002];

inline bool cmp(const elem &a,const elem &b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}

long long v[100002],prv[100002],ans[100002],n;
long long aib[100002];

long long querySum(long long poz) {
  long long answer = 0;
  for (int i = poz; i > 0; i -= i & -i)
    answer += aib[i];
  return answer;
}

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


int main()
{
    long long m,k,i,j;
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
        update(i,v[i]);
    }
    for(i=1;i<=m;i++)
        fin>>w[i].st>>w[i].dr,w[i].index=i;
    sort(w+1,w+m+1,cmp);
    i=1;
    for(j=1;j<=m;j++)
    {
        while(i<=w[j].dr)
        {
            if(prv[v[i]]!=0)
                update(prv[v[i]],-v[i]);
            prv[v[i]]=i;
            i++;
        }
        ans[w[j].index]=querySum(w[j].dr)-querySum(w[j].st-1);
    }
    for(i=1;i<=m;i++)
        fout<<ans[i]%MOD<<'\n';
    return 0;
}