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

const int nmax = 100000;
const int mod = 666013;
const int sqn = 400;

long long a[nmax + 5];


int f[nmax + 5];
int v[nmax + 5];
int sol[nmax + 5];
int n;
int k;
void update(int poz,long long val)
{
    for(; poz<=nmax; poz+=(poz&(-poz)))
        a[poz]=(a[poz]+val)%mod;
}
long long query(int poz)
{
    long long s=0;
    for(; poz>0; poz-=(poz&(-poz)))
        s=(s+a[poz])%mod;
    return s;
}

struct qqq
{
    int x;
    int y;
    int ind;
};

vector <qqq> q[sqn+5];

int bl;
int nrb;


int m;

int main()
{
    fin>>n>>k>>m;
    bl = sqrt(n*2);
    nrb = n/bl + (n%bl!=0);
    for(int i=1; i<=n; i++)
        fin>>v[i];
    for(int i=1; i<=m; i++)
    {
        qqq x;
        fin>>x.x>>x.y;
        x.ind=i;
        q[x.x/bl+1].push_back(x);
    }
    for(int i=1; i<=nrb; i++)
        if(q[i].empty()==false)
            sort(q[i].begin(),q[i].end(),[](qqq a,qqq b)
        {
            return a.y<b.y;
        });

    for(int i=1; i<=nrb; i++)
        if(q[i].empty()==false)
        {
            memset(a,0,sizeof(a));
            memset(f,0,sizeof(f));
            int dr = i * bl;
            for(auto& j : q[i])
            {
                while(dr <= j.y)
                {
                    if(f[v[dr]]==0)
                        update(v[dr],v[dr]);
                    f[v[dr]]++;
                    dr++;
                }
                sol[j.ind] = query(nmax);
                for(int st = j.x; st<min(j.y+1,i*bl); st++)
                {
                    if( f[v[st]] == 0)
                        sol[j.ind]=(sol[j.ind] + v[st])%mod;
                    f[v[st]]++;
                }
                for(int st = j.x; st<min(j.y+1,i*bl); st++)
                    f[v[st]]--;

            }
        }
    for(int i=1; i<=m; i++)
        fout<<sol[i]<<'\n';

}