#include<cstdio>
#include<fstream>
#include<algorithm>
#define MOD 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
struct elem
{
    long long st,dr,index;
};
elem q[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],sol[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 add) {
  for (int i = poz; i <= n; i += i & -i)
    AIB[i] += add;
}


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