#include <fstream>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

int i,j,n,m,k,l,f,g,c[100000],fcv;
long long v[100000],s[100000];
const int mod=666013;

int main()
{
    fin>>n>>k>>m;
    for(l=1;l<=n;l++)
    {
        fin>>v[l];
    }
    for(l=1;l<=m;l++)
    {
        for(g=1;g<=k;g++)   c[g]=0;
        fin>>i>>j;
        for(f=i;f<=j;f++)
        {
            fcv=v[f];
            if(c[fcv]==0)
                s[l]=s[l]+v[f];

            c[fcv]++;
        }
        fout<<s[l]%mod<<'\n';
    }
    return 0;
}