#include <iostream>
#include <fstream>
#include <algorithm>

#define int long long

using namespace std;

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

struct query{
    int st, dr, order;
};

bool cmp1(query a, query b){
    return a.dr < b.dr;
}

const int N = 1e5, buff = 10, mod = 666013;
int aib[N + buff], v[N + buff], rasp_aux[N + buff], uap[N + buff], rasp[N + buff];
query q[N + buff];

int lsb(int x){return x & -x;};

void update(int poz, int val){
    if(poz)
        for(int i = poz; i <= N; i += lsb(i)) aib[i] += val;
}

int query(int poz){
    int ans = 0;
    for(int i = poz; i > 0; i -= lsb(i)) ans += aib[i];
    return ans;
}

signed main(){
    int n, k, m, ind = 1;
    fin >> n >> k >> m;
    for(int i = 1; i <= n; i++) fin >> v[i];
    for(int i = 1; i <= m; i++) fin >> q[i].st >> q[i].dr, q[i].order = i;
    sort(q + 1, q + m + 1, cmp1);
    for(int i = 1; i <= m; i++){
        while(ind <= q[i].dr){
            update(ind, v[ind]);
            update(uap[v[ind]], -v[ind]);
            uap[v[ind]] = ind;
            ind++;
        }
        rasp_aux[i] = query(q[i].dr) - query(q[i].st - 1);
    }
    for(int i = 1; i <= m; i++)
        rasp[q[i].order] = rasp_aux[i];
    for(int i = 1; i <= m; i++)
        fout << (rasp[i] % mod) << '\n';
    return 0;
}