#include <fstream>
#include <vector>
#define modulo 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int aib[100001], x, i, m, n, k, j, a, b, sum;
vector <int> vec[100001];
void update(int x, int value){
    while(x <= n){
        aib[x] += value;
        x += (x & (- x));
    }
}
int quary(int x){
    int s = 0;
    while(x >= 1){
        s = (s + aib[x]) % modulo;
        x -= (x & (- x));
    }
    return s;
}
int main()
{   f >> n >> k >> m;
    for(i = 1; i <= n; i++){
        f >> x;
        vec[x].push_back(i);
        update(i, x);
    }
    for(i = 1; i <= k; i++){
        for(j = 0; j < vec[i].size() - 1; j++)
            update(vec[i][j], -i);
    }
    for(i = 1; i <= m; i++){
        f >> a >> b;
        sum = quary(b) - quary(a - 1);
        if(sum < 0)
            sum += modulo;
        g << sum << '\n';
    }
    return 0;
}