#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 666013;
int aib[100005];
int v[100005];
int last[100005];
struct Queries
{
    int x,y,ind;
} que[100005];
int n;
void update(int poz, int val)
{
    if(poz==0){
        aib[0]=(aib[0]+val+mod)%mod;
        return;
    }
    for(; poz<=n; poz+=poz&-poz)
        aib[poz]=(aib[poz]+val+mod)%mod;
}
int query(int poz)
{
    int s=0;
    for(; poz>0; poz-=poz&-poz)
        s=(s+aib[poz]+mod)%mod;
    return s;
}
bool cmp(const Queries &a, const Queries &b)
{
    return a.y<b.y;
}
int sol[100005];
int main()
{   freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    int k,m,i,j;
    scanf("%d%d%d", &n, &k, &m);
    for(i=1; i<=n; i++)
        scanf("%d", &v[i]);
    for(i=1; i<=m; i++){
        scanf("%d%d", &que[i].x, &que[i].y);
        que[i].ind=i;
    }
    sort(que+1, que+m+1,cmp);
    for(i=1,j=1; i<=m; i++){
        while(j<=que[i].y){
            update(last[v[j]], -v[j]);
            update(j, v[j]);
            last[v[j]]=j;
            j++;
        }
        sol[que[i].ind]=(query(que[i].y)-query(que[i].x-1)+mod)%mod;
    }
    for(i=1; i<=m; i++)
        printf("%d\n", sol[i]);
    return 0;
}