#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 100005;
const int MOD = 666013;
struct Query {
    int begin, end, index;
    inline bool operator<(const Query &other) const {
        return end < other.end;
    }
} queries[MAX_N];
long long aib[MAX_N];
long long answer[MAX_N];
int a[MAX_N];
int pos[MAX_N];

void update_aib(int pos, int val, int n) {
    for(int i = pos; i <= n; i += (i & (-i))) {
        aib[i] += val;
    }
}
long long query_aib(int pos) {
    long long answer = 0;
    for(int i = pos; i; i -= (i & (-i))) {
        answer += aib[i];
    }
    return answer;
}

int main() {
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    int n, k, m;
    fin >> n >> k >> m;
    for(int i = 1; i <= n; ++ i) {
        fin >> a[i];
        update_aib(i, a[i], n);
    }
    for(int i = 1; i <= m; ++ i) {
        fin >> queries[i].begin >> queries[i].end;
        queries[i].index = i;
    }
    sort(queries + 1, queries + m + 1);
    int u = 0;
    for(int i = 1; i <= m; ++ i) {
        while(u < queries[i].end) {
            ++ u;
            if(pos[a[u]] != 0) {
                update_aib(pos[a[u]], -a[u], n);
            }
            pos[a[u]] = u;
        }
        answer[queries[i].index] = query_aib(queries[i].end) - query_aib(queries[i].begin - 1);
    }
    for(int i = 1; i <= m; ++ i) {
        fout << answer[i] % MOD << "\n";
    }
    return 0;
}