#include <iostream>
#include <fstream>
#include <algorithm>

#define maxN 100001
#define mod 666013

using namespace std;

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

struct s {int st, fin, poz;};
s a[maxN];
int n,k,m;
int v[maxN], aib[maxN], last[maxN], ans[maxN];


int zeros(int x) { return (-x)&x; }

void update(int poz, int val)
{
    if (poz==0) return;
    for (int i=poz; i<=n; i+=zeros(i))
        aib[i]+=val;
}


int query(int poz)
{
    int sum=0;
    for (; poz; poz-=zeros(poz))
        sum+=aib[poz];
    return sum;
}

bool cmp(s a, s b)
{
    return a.fin < b.fin;
}

int main()
{
    fin>>n>>k>>m;
    for (int i=1; i<=n; ++i)
        fin>>v[i];
    for (int i=1; i<=m; ++i)
        {
            fin>>a[i].st>>a[i].fin;
            a[i].poz=i;
        }
    sort(a+1, a+m+1, cmp);
    //cout<<a[1].poz;
    int i,j;
    for (i = 1, j = 1; i <= m; ++i) {
        while (j <= a[i].fin) {
            update (last[v[j]], -v[j]);
            update (j, v[j]);
            last[v[j]] = j;
            ++j;
            /*for (int i=1; i<=n; ++i) cout<<aib[i]<<" ";
            cout<<'\n';*/
        }
        ans[a[i].poz] = query (a[i].fin) - query (a[i].st - 1);
        //cout<<ans[a[i].poz]<<" ";
    }
    for (i=1; i<=m; ++i)
        fout<<ans[i]%mod<<'\n';
    return 0;
}