#include <fstream>
#include <vector>
#define modulo 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
vector <pair <int, int> > vec[100001];
vector <pair <int, int> >::iterator it;
int n, i, m, k, aib[100001], number, ok, a, b, x, sum, j;
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 >> x;
        ok = 0;
        for(it = vec[i - 1].begin(); it != vec[i - 1].end(); it++){
            int apparitons = (*it).first;
            int value = (*it).second;
            if(value == x){
                apparitons++;
                ok = 1;
            }
            vec[i].push_back({apparitons, value});
        }
        if(ok == 0)
            vec[i].push_back({1, x});
        update(i, x);
    }
    for(i = 1; i <= m; i++){
        f >> a >> b;
        sum = quary(b) - quary(a - 1);
        for(j = 0; j < vec[a - 1].size(); j++){
            int ap1 = vec[a - 1][j].first;
            int val = vec[a - 1][j].second;
            int ap2 = vec[b][j].first;
            sum = sum - (ap2 - ap1 - 1) * val;
            if(sum < 0)
            sum += modulo;
        }
        for(j = vec[a - 1].size(); j < vec[b].size(); j++){
            int ap = vec[b][j].first;
            int val = vec[b][j].second;
            sum = sum - (ap - 1) * val;
            if(sum < 0)
            sum += modulo;
        }
        g << sum << '\n';
    }
    return 0;
}