#include <bits/stdc++.h>

using namespace std;

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

int const nMax = 100005;
int const mod = 666013;

int x, y, n, k, op, m;
long long aint[4*nMax];
int a [nMax];
int lastapp [nMax];
long long ans[nMax];

vector <vector <pair <int , int >>> q;


void update(int st, int dr, int nod, int poz, int val){
    if(st == dr){
        aint[nod] = val;
        return;
    }
    int mij = (st + dr)/2;
    if( poz <= mij)
        update(st, mij, nod*2, poz, val);
    else
        update(mij+1, dr, nod*2+1, poz, val);
    aint[nod] = (aint[2*nod] + aint[2*nod+1]) %mod;
}

long long query(int st, int dr, int l, int r, int nod){
    
    if((l <= st && r >= dr)){
        return aint[nod];
    }
    int mij = (st+dr)/2;
    long long mxl = 0, mxr = 0;
    if( l <= mij)
        mxl = query(st, mij, l, r, nod*2);
    if(r > mij)
        mxr = query(mij+1, dr, l, r, nod*2+1);
    return (mxl+ mxr)%mod;


}

int main()
{
    fin >> n >> k >> m;

    for(int i = 1; i <= n; i++){
        fin >> a[i];
    }
    q.resize(n+1);
    for( int i = 1; i <= m; i++){
        fin >> x >> y;
        q[y].push_back({i, x});
    }

    for( int i = 1; i <= n ; i++){
        if(lastapp[a[i]] != 0){
            update(1, n, 1, lastapp[a[i]], 0);
        }
        update(1, n, 1, i, a[i]);
        lastapp[a[i]] = i;


        if(q[i].size() > 0){
            for(auto el : q[i]){
               // cout << i << el.first << el.second;
                ans[el.first] = query(1, n, el.second, i, 1);
            }
        }
        
    }

    for(int i = 1; i <= m; i++)
        fout << ans[i] << "\n";

    return 0;
}