#include<bits/stdc++.h>
#define int long long
#define MOD 666013
using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

int v[100005],lastpoz[100005],aib[100005],sol[100005],n;

struct cv
{
    int st,dr,poz;
}a[100005];

int cmp(cv a, cv b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}

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

int querysum(int poz)
{
    int i,s=0;
    for(i=poz;i>=1;i-=(i&-i))
        s+=aib[i];
    return s;
}

signed main()
{
    int k,m,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>>a[i].st>>a[i].dr;
        a[i].poz=i;
    }
    sort(a+1,a+m+1,cmp);
    i=1;
    for(j=1;j<=m;j++)
    {
        while(i<=a[j].dr)
        {
            if(lastpoz[v[i]]!=0)
                update(lastpoz[v[i]],-v[i]);
            lastpoz[v[i]]=i;
            i++;
        }
        sol[a[j].poz]=querysum(a[j].dr)-querysum(a[j].st-1);
    }
    for(i=1;i<=m;i++)
        g<<sol[i]%MOD<<'\n';
    return 0;
}