#include <fstream>
#include <iostream>
#include <vector>
#include <climits>
#include <bits/stdc++.h>
using namespace std;
const int Vmax = 100001;
const int MODUL = 666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct queries{
    int st;
    int dr;
    int ind;
};

int n, k, m, val[Vmax], sol[Vmax], active[4 * Vmax];;
vector<int> lastPos(Vmax, -1);

void build(int nod, int st, int dr){
    if(st == dr){
        active[nod] = val[st];
        return;
    }
    int mij = (st+dr)/2;
    build(2*nod, st, mij);
    build(2*nod+1, mij+1, dr);
    active[nod] = active[2*nod] + active[2*nod+1];
}

void update(int nod, int st, int dr, int x, int valoare){
    if(st==dr){
        active[nod] = valoare;
        return;
    }
    int mij = (st+dr)/2;
    if(x<=mij)
        update(2*nod, st, mij, x, valoare);
    else
        update(2*nod+1, mij+1, dr, x, valoare);
    active[nod] = active[2*nod] + active[2*nod+1];
}

int queryAnswer(int nod, int st, int dr, int x, int y, vector<int> &suma){
    if(st == x && dr == y){
        return active[nod];
    }
    int mij = (st+dr)/2;
    if(y<=mij)
        return queryAnswer(2*nod, st, mij, x, y, suma);
    else if(x>mij)
        return queryAnswer(2*nod+1, mij+1, dr, x, y, suma);
    else
        return queryAnswer(2*nod, st, mij, x, mij, suma) + queryAnswer(2*nod+1, mij+1, dr, mij+1, y, suma);
}

int main(){
    fin>>n>>k>>m;
    vector<queries> query(m, {Vmax, Vmax, Vmax});
    for(int i=0;i<n;i++)
        fin>>val[i];
    for(int j=0;j<m;j++){
        fin>>query[j].st;
        query[j].st--;
        fin>>query[j].dr;
        query[j].dr--;
        query[j].ind=j;
    }
    sort(query.begin(), query.end(), [](const queries& a, const queries& b){
            return a.dr < b.dr;
    });
    int j=0;
    for(int i=0;i<m;i++){
        vector<int> suma;
        int sumaFinala = 0;
        while(j<=query[i].dr){
            update(1, 0, n-1, j, val[j]);
            if(lastPos[val[j]]!=-1){
                update(1, 0, n-1, lastPos[val[j]], 0);
            }
            lastPos[val[j]] = j;
            j++;
        }
        sumaFinala = queryAnswer(1, 0, n-1, query[i].st, query[i].dr, suma);
        sol[query[i].ind] = sumaFinala % MODUL;
    }
    for(int i=0;i<m;i++){
        fout<<sol[i]<<'\n';
    }
    return 0;
}