#include <bits/stdc++.h>
using namespace std;
#define MOD 600013
class AIB{
private:
    vector<long long>tree;
    int n;
public:
    AIB(int size):n(size),tree(size+1,0){}
    void update(int pos,long long val){
        for(int i=pos;i<=n;i+=i&(-i))
            tree[i]=(tree[i]+val)%MOD;
    }
    long long query(int pos){
        long long sum=0;
        for(int i=pos;i>0;i-=i&(-i))
            sum=(sum+tree[i])%MOD;
        return sum;
    }
    long long rangeQuery(int l,int r){
        if(l>r)
            return 0;
        long long res=query(r)-query(l-1);
        return (res%MOD+MOD)%MOD;
    }
};
int main(){
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");
    int n,k,m,i,q,j,pos;
    long long sum;
    cin >> n >> k >> m;
    vector<int> v(n+1);
    for(i=1;i<=n;i++)
        cin >> v[i];
    AIB aib(n);
    for(q=0;q<m;q++){
        cin >> i >> j;
        AIB tempAIB(k);
        vector<bool>seen(k+1,false);
        sum=0;
        for(pos=i;pos<=j;pos++)
            if(!seen[v[pos]]){
                seen[v[pos]]=true;
                sum=(sum+v[pos])%MOD;
            }
        cout << sum << "\n";
    }
    return 0;
}