#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 666013;

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

struct Events{
    int st, dr, pos;
};

int N, M, K;
vector<Events> events;
vector<int> v, BIT, lastPOS, ans;

void update(int x, int val){
    for(int i=x; i<=N; i+=i&-i)
        BIT[i] = (BIT[i]+val+MOD)%MOD;
}

int query(int x){
    int sum=0;
    for(int i=x; i>=1; i-=i&-i)
        sum = (sum+BIT[i]+MOD)%MOD; ///for 

    return sum;
}

bool cmp(Events a, Events b){
    if(a.dr == b.dr) return a.st<b.st;
    return a.dr < b.dr;
}

int main()
{
    int i, j;

    cin>>N>>K>>M;

    v.resize(N+1);
    ans.resize(M+1);
    BIT.resize(N+1, 0);
    events.resize(M+1);
    lastPOS.resize(K+1, 0);

    for(i=1; i<=N; i++){
        cin>>v[i];
    }

    for(i=1; i<=M; i++){
        cin>>events[i].st>>events[i].dr;
        events[i].pos = i;
    }

    sort(events.begin(), events.end(), cmp);

    for(i=1; i<=M; i++){
        for(j=events[i-1].dr+1; j<=events[i].dr; j++){
            int x = v[j];
            if(lastPOS[x] > 0){
                update(lastPOS[x], -v[j]);
            }

            lastPOS[x] = j;
            update(j, v[j]);
        }
        ans[events[i].pos] = query(events[i].dr)-query(events[i].st-1);
    }

    for(i=1; i<=M; i++)
        cout<<ans[i]<<'\n';
}