#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define int long long
const int K=666013;
int n,i,k,v[100001],up[100001],aib[100001],p,m;
struct query
{
    int f,s,ind;
    long long r;
};
query q[100001];
bool cmp(query a,query b)
{
    if(a.s<b.s)
        return true;
    if(a.s==b.s)
    {
        if(a.f>b.f)
            return true;
    }
    return false;
}
void update(int poz,int val)
{
    while(poz<=n)
    {
        aib[poz]+=val;
        poz+=(poz&(-poz));
    }
}
int sp(int a)
{
    int sa=0;
    while(a)
    {
        sa+=aib[a];
        a-=(a&(-a));
    }
    return sa;
}
int Query(int a,int b)
{
    return sp(b)-sp(a-1);
}
bool cmp2(query a,query b)
{
    return a.ind<b.ind;
}
int32_t main()
{
    fin>>n>>k>>m;
    for(i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    for(i=1; i<=m; i++)
    {
        fin>>q[i].f>>q[i].s;
        q[i].ind=i;
    }
    sort(q+1,q+m+1,cmp);
    p=1;
    for(i=1; i<=n; i++)
    {
        if(up[v[i]])
            update(up[v[i]],-v[i]);
        up[v[i]]=i;
        update(i,v[i]);
        //for(int j=1;j<=n;j++)
        //    fout<<aib[j]<<" ";
        //fout<<"\n";
        while(q[p].s==i)
        {
            q[p].r=Query(q[p].f,i);
            p++;
        }
    }
    sort(q+1,q+m+1,cmp2);
    for(i=1; i<=m; i++)
        fout<<q[i].r%K<<"\n";
}