#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int nmax = 100000;
const int mod = 666013;
const int sqn = 400;




int v[nmax + 5];
int sol[nmax + 5];
int n;
int k;

struct qqq{
int x;
int y;
int ind;
}q[nmax + 5];

int m;

long long a[nmax  * 4 + 5];
int l[nmax + 5];

void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        a[nod] = val;
        return;
    }
    int mid = (st+dr)/2;
    if(poz<=mid)
        update(nod*2,st,mid,poz,val);
    if(poz>mid)
        update(nod*2+1,mid+1,dr,poz,val);
    a[nod]=(a[nod*2]+a[nod*2+1])%mod;
}
int query(int nod,int st,int dr,int x,int y)
{
    if(x<=st && dr<=y)
        return a[nod];
    int mid = (st+dr)/2;
    int s1 = 0;
    int s2 = 0;
    if(x<=mid)
        s1 = query(nod*2,st,mid,x,y);
    if(y>mid)
        s2 = query(nod*2+1,mid+1,dr,x,y);
    return (s1+s2)%mod;
}


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

    for(int i=1;i<=m;i++){
        fin>>q[i].x>>q[i].y;
        q[i].ind = i;
    }
   sort(q+1,q+m+1,[](qqq a,qqq b){return a.y<b.y;});
   int dr = 1;
   for(int i=1;i<=m;i++){
        while(dr <= q[i].y)
        {
            if(l[v[dr]])
                update(1,1,n,l[v[dr]],0);
            l[v[dr]]=dr;
            update(1,1,n,dr,v[dr]);
            dr++;
        }
        sol[q[i].ind] = query(1,1,n,q[i].x,q[i].y);
   }
   for(int i=1;i<=m;i++)
    fout<<sol[i]<<'\n';




}