#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int mod=666013;
int aib[100005],a[100005],lst[100005],ans[100005];
vector< pair<int,int> >v[100005];
int i,n,m,x,y,k,j;
inline int lbit(int x)
{
    return (((x^(x-1))&x));
}
void update(int x,int val)
{
    if(x==0) return;
    for(int poz=x;poz<=n;poz+=lbit(poz))
        {
        aib[poz]+=val;
        if(aib[poz]>=mod) aib[poz]-=mod;
        if(aib[poz]<0) aib[poz]+=mod;
        }
}
int compute(int x)
{
    int sum=0;
    for(int poz=x;poz>0;poz-=lbit(poz))
    {
        sum+=aib[poz];
        if(sum>=mod) sum-=mod;
    }
    return sum;
}
int main()
{
    ifstream f("distincte.in");
    ofstream g("distincte.out");
    f>>n>>k>>m;
    for(i=1;i<=n;i++)
        f>>a[i];
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[y].push_back(make_pair(x,i));
    }
    for(i=1;i<=n;i++)
    {
        update(lst[a[i]],-a[i]);
        lst[a[i]]=i;
        update(i,a[i]);
        for(j=0;j<v[i].size();j++)
        {
            ans[v[i][j].second]=compute(i)-compute(v[i][j].first-1);
            if(ans[v[i][j].second]<0) ans[v[i][j].second]+=mod;
        }
    }
    for(i=1;i<=m;i++)
        g<<ans[i]<<'\n';
    return 0;
}