#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 v[nmax + 5];
int sol[nmax + 5];
int n;

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;
}

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

vector <qqq> q[sqn+5];

int bl;
int nrb;

int k;
int m;

int main()
{
    fin>>n>>k>>m;
    bl = sqrt(n);
    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));
            int dr = i * bl;
            for(auto& j : q[i])
            {
                while(dr <= j.y){
                    if(query(v[dr])-query(v[dr]-1)==0)
                        update(v[dr],v[dr]);
                    dr++;
                }
                sol[j.ind] = query(nmax);
                for(int st = j.x;st<min(j.y+1,i*bl);st++)
                    if(query(v[st])-query(v[st]-1) == 0)
                        sol[j.ind]+=v[st];
            }
        }
    for(int i=1;i<=m;i++)
        fout<<sol[i]<<'\n';

}