#include <fstream>
#include <algorithm>
#include <iostream>

#define lsb(x) (x&(-x))
#define mod(a) (a = (a >= mod ? a - mod : a))
using namespace std;


ifstream in("distincte.in");
ofstream out("distincte.out");
struct state{
    pair<int,int> capete;
    int ord;
};

const int maxn = 100100;
const int mod = 666013;

state Q[maxn];
int n,k,m;
int v[maxn];
int last[maxn];
int show[maxn];
int AIB[maxn];

inline void update(int wher,const int &val){
    for(;wher<=n;wher += lsb(wher)){
        AIB[wher] += val;
        mod(AIB[wher]);
    }
}

inline int query(int wher){
    int ret = 0;
    for(;wher>0;wher -= lsb(wher)){
        ret += AIB[wher];
        mod(ret);
    }
    return ret;
}

bool comp(const state&a,const state&b){
    return a.capete.second < b.capete.second;
}
int main()
{
    in >> n >> k >> m;
    int i,j;
    for(i=1;i<=n;++i)
        in >> v[i];
    for(i=1;i<=m;++i){
        in >> Q[i].capete.first >> Q[i].capete.second;
        Q[i].ord = i;
    }
    sort(Q+1,Q+i,comp);
    for(i=1;i<=m;++i){
        for(j=Q[i-1].capete.second+1;j <= Q[i].capete.second;++j){
            if(last[v[j]]){
                update(last[v[j]],-v[j]);
            }
            update(last[v[j]]=j,v[j]);
        }
        show[Q[i].ord] = query(Q[i].capete.second) - query(Q[i].capete.first-1);
        mod(show[Q[i].ord]);
    }
    for(i=1;i<=m;++i)
        out << show[i] << "\n";
    return 0;
}