#include <bits/stdc++.h>

using namespace std;

const long long NMAX = 100001;

long long aib[NMAX];

void update(long long node, long long x){
    for(; node < NMAX; node += node&(-node))
        aib[node] += x;
}

long long query(long long node){
    if(node == 0)
        return 0;
    long long s = 0;
    for(; node > 0; node -= node&(-node))
        s += aib[node];
    return s;
}

vector <pair <long long, long long> > q[NMAX];
long long last[NMAX];
long long v[NMAX];
long long sol[NMAX];

int main()
{
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");
    long long n, k, m, i;
    cin >> n >> k >> m;
    for(long long i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(long long i = 1; i <= m; i++){
        long long a, b;
        cin >> a >> b;
        q[b].push_back({a, i});
    }
    for(long long i = 1; i <= n; i++){
        if(last[v[i]] != 0)
            update(last[v[i]], -v[i]);
        update(i, v[i]);
        last[v[i]] = i;
        long long aici = query(i);
        for(auto x : q[i]){
            sol[x.second] = aici - query(x.first - 1);
        }
    }
    for(long long i = 1; i <= m; i++)
        cout << sol[i] % 666013 << "\n";
    return 0;
}