#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int NMAX=1e5;
int n, k, m;
vector<int> v, last_position, ans;
vector<tuple<int,int,int> > q;
struct AINT{
    int arbore[4*NMAX+5];
    void update(int poz, int val, int left=1, int right=n, int node=1){
        if(left==right){
            arbore[node]=val%mod;
            return;
        }
        int mid=(left+right)/2;
        if(poz<=mid){
            update(poz, val, left, mid, 2*node);
        }else{
            update(poz, val, mid+1, right, 2*node+1);
        }
        arbore[node]=(arbore[2*node]+arbore[2*node+1])%mod;
    }
    int query(int a, int b, int left=1, int right=n, int node=1){
        if(left>b or right<a){
            return 0;
        }
        if(left>=a and right<=b){
            return arbore[node]%mod;
        }
        int mid=(left+right)/2;
        return (query(a, b, left, mid, 2*node)+query(a, b, mid+1, right, 2*node+1))%mod;
    }
};
signed main(){
    fin>>n>>k>>m;
    v.resize(n+1);
    q.resize(m+1);
    ans.resize(m+1);
    last_position.resize(n+1, 0);
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    for(int i=1;i<=m;i++){
        fin>>get<1>(q[i])>>get<0>(q[i]);//0 - dr, 1 - st, 2 - idx
        get<2>(q[i])=i;
    }
    sort(q.begin(),q.end());
    int p=1;
    AINT aint;
    for(int i=1;i<=m;i++){
        while(p<=get<0>(q[i])){
            aint.update(p, v[p]);
            if(last_position[v[p]]!=0){
                aint.update(last_position[v[p]], 0);
            }
            last_position[v[p]]=p;
            p++;
        }
        ans[get<2>(q[i])]=aint.query(get<1>(q[i]), get<0>(q[i]));
    }
    for(int i=1;i<=m;i++){
        fout<<ans[i]<<'\n';
    }
}