#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
#include <cmath>

///#include <tryhardmode>
///#include <GODMODE::ON>
///DAU PENTRU TITANS RO017

using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

const int NMAX=1e5+5;
const int MOD=666013;

int v[NMAX];

int block;
int rez[NMAX];

struct elem{
    int st;
    int dr;
    int ind;
}query[NMAX];

bool cmp(elem a,elem b)
{
    if(a.st/block!=b.st/block)
        return a.st/block<b.st/block;
    return a.dr<b.dr;
}

void solve_q(int q)
{
    int i,st=1,dr=0;
    long long total=0;
    map<int,int>mp;
    for(i=1;i<=q;i++)
    {
        while(dr<query[i].dr)
        {
            mp[v[dr+1]]++;
            if(mp[v[dr+1]]==1)
                total=(total+v[dr+1])%MOD;
            dr++;
        }
        while(dr>query[i].dr)
        {
            mp[v[dr]]--;
            if(mp[v[dr]]==0)
            {
                total-=v[dr];
                mp.erase(v[dr]);
            }
            dr--;
        }
        while(st<query[i].st)
        {
            mp[v[st]]--;
            if(mp[v[st]]==0)
            {
                total-=v[st];
                mp.erase(v[st]);
            }
            st++;
        }
        while(st>query[i].st)
        {
            mp[v[st-1]]++;
            if(mp[v[st-1]]==1)
                total=(total+v[st-1])%MOD;
            st--;
        }
        rez[query[i].ind]=total;
    }
}

int main()
{
    int n,m,i,j,k;
    fin>>n>>k>>m;
    block=(int)sqrt(n);
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=1;i<=m;i++)
    {
        fin>>query[i].st;
        fin>>query[i].dr;
        query[i].ind=i;
    }
    sort(query+1,query+m+1,cmp);
    solve_q(m);
    for(i=1;i<=m;i++)
        fout<<rez[i]<<"\n";
    return 0;
}