#include<fstream>
#include<algorithm>
#define DN 100005
#define M 666013
#define x second
#define y first
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
long long n,k,m,r[DN],s[DN],z[DN],poz,fr[DN],l[DN],val,rez[DN];
pair<int,pair<int,int>  >a[DN];
void update(int poz)
{
    while(poz<=n)
    {
        r[poz]+=val;
        poz+=(poz&(-poz));
    }
}
long long query(int poz)
{
    long long s=0;
    while(poz)
    {
        s+=r[poz];
        poz-=(poz&(-poz));
    }
    return s;
}
int main()
{
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        fin>>z[i];
    for(int i=1;i<=m;i++)
    {
        a[i].x.y=i;
        fin>>a[i].x.x>>a[i].y;
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)
    {
        while(poz<a[i].y)
        {
            poz++;
            fr[z[poz]]++;
            if(fr[z[poz]]==1)
            {
                l[z[poz]]=poz;
                val=z[poz];
                update(poz);
            }
            else
            {
                val=-z[poz];
                update(l[z[poz]]);
                l[z[poz]]=poz;
                val=z[poz];
                update(poz);
            }
        }
        rez[a[i].x.y]=(query(a[i].y)-query(a[i].x.x-1))%M;
    }
    for(int i=1;i<=m;i++)
        fout<<rez[i]<<'\n';
}