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

const int mod = 666013;

int aib[100005], v[100005];

void update(int poz, int val){
    while(poz <= 100000){
        aib[poz] += val;
        poz += (poz & -poz);
    }
}

int queryy(int poz){
    int here = 0;
    while(poz > 0){
        here += aib[poz];
        poz -= poz & -poz;
    }
    return here;
}

int ans[100005], last[100005];

struct query{
    int l, r;
}q[100005];

vector<int> qs[100005];

signed main(){

    ifstream cin("distincte.in");
    ofstream cout("distincte.out");

    int n, m, k;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        last[i] = -1;
    }
    for(int i = 1; i <= m; i++){
        cin >> q[i].l >> q[i].r;
        qs[q[i].r].push_back(i);
    }
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(last[v[i]] == -1){
            sum += v[i];
            update(i, v[i]);
        }
        else{
            update(i, v[i]);
            update(last[v[i]], -v[i]);
        }
        last[v[i]] = i;
        for(int id : qs[i]){
            ans[id] = queryy(q[id].r) - queryy(q[id].l - 1);
        }
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] % mod << '\n';

    return 0;
}