#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
const int MOD = 666013;
int n, m, k;
struct Triplet{
    int x, y, z;
};
bool comp(Triplet a, Triplet b){
    return a.y < b.y;
}
vector<int> aib;
void update(int poz, int val){
    for(int i=poz; i<=n; i+=(i & (-i)))
        aib[i] = (aib[i] + val) % MOD;
}
int query(int x){
    int sum=0;
    for(int i=x; i>0; i-=(i & (-i)))
        sum = (sum + aib[i]) % MOD;
    
    return sum;
}
int main(){
    cin>>n>>k>>m;
    vector<int> v(n+1);
    vector<int> last(k+1);
    vector<int> r(m+1);
    aib.resize(n + 1);

    for(int i=1; i<=n; i++)
        cin>>v[i];
    
    vector<Triplet> q(m);
    for(int i=0; i<m; i++)
        cin>>q[i].x>>q[i].y, q[i].z = i;

    sort(q.begin(), q.end(), comp);

    int p = 0;
    for(int i=1; i<=n; i++){
        if(last[v[i]])
            update(last[v[i]], -v[i]);

        update(i, v[i]);
        last[v[i]] = i;

        while(p < m and i >= q[p].y){
            r[q[p].z] = (query(q[p].y) - query(q[p].x - 1)) % MOD;
            p++;
        }
    }

    for(int i=0; i<m; i++)
        cout<<r[i]<<'\n';
    return 0;
}