#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <algorithm>

#define mp make_pair
#define MAXN 100005
#define MOD 666013

using namespace std;
typedef int64_t var;

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

var n, k, m;

inline var zeros(const var &n) {
    return n & (-n);
}

var TREE[MAXN];
inline void add(var ind, var val) {
    for(;ind<=n;ind+=zeros(ind)) {
        TREE[ind] += val + MOD;
        TREE[ind] %= MOD;
    }
}

inline var query(var ind) {
    var sum = 0;
    for(;ind;ind-=zeros(ind)) {
        sum += TREE[ind];
        sum %= MOD;
    }
    return sum;
}

struct Query{
    var b, e, ind;
    Query(var a, var x, var c) {
        b = a;
        e = x;
        ind = c;
    }
};
vector<Query> QUERIES;

var V[MAXN], PI[MAXN], SOL[MAXN];

int main() {
    var a, b;
    fin>>n>>k>>m;
    for(var i=1; i<=n; i++) {
        fin>>V[i];
    }
    for(var i=1; i<=m; i++) {
        fin>>a>>b;
        QUERIES.push_back(Query(a, b, i));
    }

    sort(QUERIES.begin(), QUERIES.end(), [](const Query &a, const Query &b) {
            return a.e < b.e;
         });

    var olde = 0;
    for(auto q : QUERIES) {
        var e = q.e,
            b = q.b;
        for(var i=olde+1; i<=e; i++) {
            if(PI[V[i]])
                add(PI[V[i]], MOD-V[i]);
            add(i, V[i]);
            PI[V[i]] = i;
        }
        SOL[q.ind] = (query(e) - query(b-1) + MOD) % MOD;
        olde = e;
    }

    for(var i=1; i<=m; i++) {
        fout<<SOL[i]<<'\n';
    }

    return 0;
}