#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int N=100009;
struct xd
{
    int x,y,poz;
}a[N];
int compare(xd a,xd b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    else
        return a.x<b.x;
}
int n,m,k;
int aib[N],v[N],last[N],ans[N];
void add(int x,int y)
{
    while(x<=n)
    {
        aib[x]+=y;
        x+=x&(-x);
    }
}
int query(int x)
{
    int sum=0;
    while(x)
    {
        sum+=aib[x];
        sum%=mod;
        x-=x&(-x);
    }
    return sum;
}
void solve()
{
    sort(a+1,a+m+1,compare);
    for(int i=1;i<=m
    ;i++)
    {
        for(int j=a[i-1].y+1;j<=a[i].y;j++)
        {
            if(last[v[j]])
                add(last[v[j]],-v[j]);
            last[v[j]]=j;
            add(last[v[j]],v[j]);
        }
        ans[a[i].poz]=query(a[i].y)-query(a[i].x-1);
        if(ans[a[i].poz]<0)
            ans[a[i].poz]+=mod;
    }
    for(int i=1;i<=m;i++)
        fout<<ans[i]<<'\n';
}
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].x>>a[i].y,a[i].poz=i;
    solve();
    return 0;
}