#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

int n,m,k,a[100005],s[100005];
ifstream fin("distincte.in");
ofstream fout("distincte.out");

int Suma(int st,int dr)
{
    int i,k=0,aux[100004],s=0;
    for(i=st;i<=dr;i++)
        aux[++k]=a[i];
    sort(aux+1,aux+k+1);
    for(i=1;i<=k;i++)
        if(aux[i]!=aux[i+1])s+=aux[i];
    s=s%MOD;
    return s;
}
int main()
{
    int i,x,y;
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
        fin>>a[i];
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<Suma(x,y)<<"\n";
    }
    return 0;
}