/// ATENTIE
// Solutie care poate cauza atac emotional
// si poate ingreuna starea de spirit
// Continua cu atentie
#include <bits/stdc++.h>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int mod=666013;
#define int long long
int n, k, m, v[100001], x, y, blen, fr[100001], sumcur;
int rez[100001];
struct intreb
{
    int l, r, id;
};
vector<intreb>q;
bool cmp(intreb a, intreb b)
{
    if (a.l/blen==b.l/blen)
    {
        return a.r<b.r;
    }
    return a.l/blen<b.l/blen;
}

signed main()
{
    fin>>n>>k>>m;
    blen=(int)sqrt((float(n)));
    for (int i=1; i<=n; i++)
    {
        fin>>v[i];

    }
    for (int i=1; i<=m; i++)
    {
        intreb xx;
        fin>>xx.l>>xx.r;
        xx.id=i;
        q.push_back(xx);
    }
    sort(q.begin(), q.end(), cmp);
    int left=1, right=0;
    for (intreb qr : q)
    {
        while (right<qr.r)
        {
            right++;
            int val=v[right];
            fr[val]++;
            if (fr[val]==1)
            {
                sumcur+=val;
            }
        }
        while(left>qr.l)
        {
            left--;
            int val=v[left];
            fr[val]++;
            if (fr[val]==1)
            {
                sumcur+=val;
            }
        }
        while (right>qr.r)
        {
            int val=v[right];
            fr[val]--;
            if (fr[val]==0)
            {
                sumcur-=val;
            }
            right--;
        }
        while (left<qr.l)
        {
            int val=v[left];
            fr[val]--;
            if (fr[val]==0)
            {
                sumcur-=val;
            }
            left++;
        }
        rez[qr.id]=sumcur%mod;
    }
    for (int i=1; i<=m; i++)
    {
        fout<<rez[i]<<'\n';
    }


    return 0;
}