#include <bits/stdc++.h>
using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int kMax = 100001;
const int MOD = 666013;

int n, k, m, bucket, x[kMax];
int f[kMax], result[kMax];

struct data {
    int left, right, ind;
} v[kMax];

bool comp(data a, data b) {

    if (a.left / bucket != b.left / bucket)
        return (a.left / bucket) < (b.left / bucket);

    return a.right < b.right;

}

int main() {

    fin >> n >> k >> m;

    bucket = (int)sqrt(n);

    for (int i = 1; i <= n; i++)
        fin >> x[i];

    for (int i = 0; i < m; i++) {
        fin >> v[i].left >> v[i].right;
        v[i].ind = i;
    }

    sort(v, v + m, comp);

    int absLeft = v[0].left, absRight = v[0].right, sum = 0;

    for (int i = absLeft; i <= absRight; i++) {
        f[x[i]]++;
        if (f[x[i]] == 1)
            sum = (sum + x[i]) % MOD;
    }
    result[v[0].ind] = sum;

    for (int i = 1; i < m; i++) {
        int left = v[i].left;
        int right = v[i].right;

        while (absLeft < left) {
            if (f[x[absLeft]] > 0)
                f[x[absLeft]]--;
            if (f[x[absLeft]] == 0)
                sum = (sum - x[absLeft] + MOD) % MOD;
            absLeft++;
        }

        while (absLeft > left) {
            f[x[absLeft-1]]++;
            if (f[x[absLeft-1]] == 1)
                sum = (sum + x[absLeft-1]) % MOD;
            absLeft--;
        }

        while (absRight <= right) {
            f[x[absRight]]++;
            if (f[x[absRight]] == 1)
                sum = (sum + x[absRight]) % MOD;
            absRight++;
        }

        while (absRight > right + 1) {
            f[x[absRight-1]]++;
            if (f[x[absRight-1]] == 1)
                sum = (sum - x[absRight] + MOD) % MOD;
            absRight--;
        }

        result[v[i].ind] = sum;
    }
    for (int i = 0; i < m; i++)
        fout << result[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}