#include <fstream>
#include <algorithm>
using namespace std;
constexpr long long DIM=100010;
constexpr long long MOD=666013;
struct interval{
    long long st, dr, poz, sol;
}a[DIM];
long long v[DIM], fr[DIM], aib[DIM];
long long n,m,k;
void update(long long poz, long long val){
    for (long long i=poz;i<=n;i+=(i&-i)){
        aib[i]+=val;
    }
}
long long query(long long poz){
    long long sum=0;
    for (long long i=poz;i>0;i-=(i&-i)){
        sum+=aib[i];
    }
    return sum;
}
int main (){
    ifstream fin ("distincte.in");
    ofstream fout("distincte.out");
    fin>>n>>k>>m;
    for (long long i=1;i<=n;i++){
        fin>>v[i];
    }
    for (long long i=1;i<=m;i++){
        fin>>a[i].st>>a[i].dr;
        a[i].poz=i;
    }
    auto cmp=[](interval x, interval y){
        if (x.dr!=y.dr){
            return x.dr<y.dr;
        }
        return x.st<y.st;
    };
    sort (a+1, a+m+1, cmp);
    long long poz=1;
    for (long long i=1;i<=m;i++){
        for (long long j=poz;j<=a[i].dr;j++){
            if (fr[v[j]]==0){
                update(j, v[j]);
            }
            else{
                update(fr[v[j]], -v[j]);
                update(j, v[j]);
            }
            fr[v[j]]=j;
        }
        a[i].sol=query(a[i].dr)-query(a[i].st-1);
        poz=a[i].dr+1;
    }
    auto cmp2=[](interval x, interval y){
        return x.poz<y.poz;
    };
    sort (a+1, a+m+1, cmp2);
    for (long long i=1;i<=m;i++){
        fout<<a[i].sol%MOD<<"\n";
    }
    return 0;
}