#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,k,m,a[100001],fr[100001],rez[100001];
struct numar
{
    int ind,x,y;
};
vector <numar> buck[400];
int cmp(numar a,numar b)
{
    return a.y<b.y;
}
int main()
{
    fin>>n>>k>>m;
    int l=sqrt(n);
    int nr=n/l+(n%l!=0);
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        buck[(x/l+(x%l!=0))].push_back({i,x,y});

    }
    for(int i=1;i<=nr;i++)
    {
        sort(buck[i].begin(),buck[i].end(),cmp);
    }
    for(int p=1;p<=nr;p++)
    {
        int dr=p*l;
        memset(fr,0,sizeof(fr));
        long long s=0;
        for(auto i:buck[p])
        {
            int ind=i.ind;
            int x=i.x;
            int y=i.y;
           for(int j=x;j<=min(y,p*l);j++)
           {
               if(fr[a[j]]==0)
               {
                   s=(s+a[j])%mod;
               }
               fr[a[j]]++;

           }
           for(int j=dr;j<=y;j++)
           {
               if(fr[a[j]]==0)
               {
                   s=(s+a[j])%mod;
                   fr[a[j]]++;
               }
           }
           if(dr<y)
            dr=y;
            rez[ind]=s;
        for(int j=x;j<=min(y,p*l);j++)
           {
               if(fr[a[j]]==1)
               {
                   s=(s-a[j]+mod)%mod;
               }
               fr[a[j]]--;

           }

        }
    }
    for(int i=1;i<=m;i++)
    {
        fout<<rez[i]<<"\n";
    }

    return 0;
}