#include <bits/stdc++.h>
#define z(x) ((x)&(-x))
using namespace std;
typedef int ll;
int const N = 1e5 + 3 , mod = 666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n , k , m , a , b;
int v[N] , nxt[N] , fq[N] , ans[N] , ind[N];
ll sp[N];
pair<int , int> q[N];
int addm(int a , int b){
    return (a + b) % mod;
}
class aib{
private:
    ll v[N];
    ll sum(int p){
        ll ans = 0;
        for(int i = p ; i ; i -= z(i))
            ans = addm(ans , v[i]);
        return ans;
    }
public:
    aib(){
        fill(v , v + N , 0);
    }
    void add(int p , int x){
        for(int i = p ; i <= n ; i += z(i))
            v[i] = addm(v[i] , x);
    }
    ll query(int a , int b){
        return sum(b) - sum(a - 1);
    }
}t;
ll sum(int a , int b){
    return addm(sp[b] , mod - sp[a - 1]);
}
bool crt(int A , int B){
    return q[A] < q[B];
}
int main()
{
    fin >> n >> k >> m;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> v[i];
        sp[i] = addm(sp[i - 1] , v[i]);
    }
    fill(fq , fq + 1 + n , n + 1);
    for(int i = n ; i ; -- i){
        nxt[i] = fq[v[i]];
        fq[v[i]] = i;
    }
    fill(fq , fq + 1 + n , 0);
    for(int i = 1 ; i <= n ; ++ i){
        if(fq[v[i]])
            t.add(i , v[i]);
        fq[v[i]] = 1;
    }
    int j = 1;
    for(int i = 1 ; i <= m ; ++ i){
        fin >> a >> b;
        q[i] = make_pair(a , b);
        ind[i] = i;
    }
    sort(ind + 1 , ind + 1 + m , crt);
    for(int i = 1 ; i <= m ; ++ i){
        tie(a , b) = q[ind[i]];
        while(j < a){
            t.add(nxt[j] , -v[j]);
            ++ j;
        }
        ans[ind[i]] = addm(sum(a , b) , -t.query(a , b));
    }
    for(int i = 1 ; i <= m ; ++ i)
        fout << ans[i] << '\n';
    return 0;
}