#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
struct du{int st, dr, poz;}
a[100011];
int v[100011],n,m,k,Rez[100011],vv[100011],i,j,AIB[100011],x;
void update(int poz, int c)
{
     if (poz==0) return;
    int i;
    for(i=poz;i<=n; i+=(i&(-i)))
    {
        AIB[i]+=c;
    }
}
int query(int x)
{
    int i,val=0;
    for(i=x;i>0;i-=(i&(-i)))
    {
        val+=AIB[i];
    }
    return val;
}
bool cmp(du a, du b)
{
    return a.dr < b.dr;
}

int main()
{
    f>>n>>k>>m;
    for(i=1;i<=n;i++)
        f>>v[i];

    for (int i=1; i<=m; ++i)
        {
            f>>a[i].st>>a[i].dr;
            a[i].poz=i;
        }
    sort(a+1, a+m+1, cmp);

    int i,j;
    for (i=1,j=1;i<= m;++i) {
        while(j<=a[i].dr) {
            update (vv[v[j]],-v[j]);
            update (j,v[j]);
            vv[v[j]]=j;
            j++;
        }
  Rez[a[i].poz] = query (a[i].dr) - query (a[i].st - 1);
    }
        for (i=1; i<=m; ++i)
        g<<Rez[i]%666013<<'\n';





    return 0;
}