#include <algorithm>
#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

int v[100001], n, aib[100001], f[100001];
struct punct{
    int st, dr, poz, rez;
}a[100001];

int cmp2(punct a, punct b)
{
    if(a.poz<b.poz)
    {
        return 1;
    }
    return 0;
}

int cmp(punct a, punct b)
{
    if(a.dr==b.dr)
          return a.st<b.st;
    return a.dr<b.dr;
}

int query(int poz)
{
    int s=0;
    for(int i=poz;i>0;i-=(i&(-i)))
    {
        s=s+aib[i];
        s=s%mod;
    }
    return s;
}

void update(int poz, int val)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
    {
        aib[i]+=val;
        aib[i]=aib[i]%mod;
        if(aib[i]<0)
        {
            aib[i]+=mod;
        }
    }
}

int main()
{
    int k, m, i;
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    for(i=1;i<=m;i++)
    {
        fin>>a[i].st>>a[i].dr;
        a[i].poz=i;
    }
    sort(a+1, a+m+1, cmp);
    i=1;
    int j=1;
    while(i<=m)
    {
        while(j<=a[i].dr)
        {
            if(f[v[j]]==0)
            {
                f[v[j]]=j;
                update(j, v[j]);
            }
            else
            {
                update(f[v[j]], -v[j]);
                f[v[j]]=j;
                update(f[v[j]], v[j]);
            }
            j++;
        }
        a[i].rez=(query(a[i].dr)-query(a[i].st-1));
        if(a[i].rez<0)
            a[i].rez+=mod;
        i++;
    }
    sort(a+1, a+m+1, cmp2);
    for(i=1;i<=m;i++)
    {
        fout<<a[i].rez<<"\n";
    }
}