#include <fstream>
#include <algorithm>
#define modulo 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int i, j, n, m, k, v[100001], sol[100001], aib[100001], pos[100001];
struct meme{
    int start, finish, pos;
}in[100001];
int cmp(meme a, meme b){
    if(a.finish == b.finish)
        return a.start < b.start;
    return a.finish < b.finish;
}
void update(int x, int value){
    while(x <= n){
        aib[x] = (aib[x] + value) % modulo;
        x = x + (x & (- x));
    }
}
int quary(int x){
    int s = 0;
    while(x >= 1){
        s = (s + aib[x]) % modulo;
        x = x - (x & (- x));
    }
    return s;
}
int main()
{   f >> n >> k >> m;
    for(i = 1; i <= n; i++)
        f >> v[i];
    for(i = 1; i <= m; i++){
        f >> in[i].start >> in[i].finish;
        in[i].pos = i;
    }
    sort(in + 1, in + m + 1, cmp);
    j = 1;
    for(i = 1; i <= m; i++){
        while(j <= in[i].finish){
            update(j, v[j]);
            if(pos[v[j]] != 0)
                update(pos[v[j]], -v[j]);
            pos[v[j]] = j;
            j++;
        }
        j--;
        sol[in[i].pos] = quary(in[i].finish) - quary(in[i].start - 1);
        if(sol[in[i].pos] < 0)
            sol[in[i].pos] += modulo;
    }
    for(i = 1; i <= m; i++)
        g << sol[i] << '\n';
    return 0;
}