#include <fstream>
#include <vector>

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

long long n, m, k, i, j, v[100100], aib[100100], s;
vector<pair<long long, long long>> queries[100100];
vector<pair<long long, long long>>::iterator it;
long long qst, qdr, ans[100100], fr[100100];

int main()
{
    f >> n >> k >> m;
    for (i = 1; i <= n; i++)
        f >> v[i];
    for (i = 1; i <= m; i++) {
        f >> qst >> qdr;
        queries[qdr].push_back({qst, i});
    }
    for (i = 1; i <= n; i++) {
        if (fr[v[i]])
            for (j = fr[v[i]]; j <= n; j = j + ((j ^ (j-1)) & j))
                aib[j] = aib[j] - v[i];
        for (j = i; j <= n; j = j + ((j ^ (j-1)) & j))
            aib[j] = aib[j] + v[i];
        fr[v[i]] = i;
        for (it = queries[i].begin(); it != queries[i].end(); advance(it, 1)) {
            qst = it -> first;
            s = 0;
            for (j = i; j > 0; j = (j & (j-1))) {
                s = s + aib[j];
            }
            for (j = qst-1; j > 0; j = (j & (j-1))) {
                s = s - aib[j];
            }
            ans[it->second] = s % 666013;
        }
    }
    for (i = 1; i <= m; i++) {
        g << ans[i] << '\n';
    }
    f.close();
    g.close();
    return 0;
}