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