#include <fstream>
#include <algorithm>
#define MOD 666013
#define ll long long
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int n,k,m;
const int N=1e5+20;
int RE[N];
ll aib[N],a[N],ult[N];
void update_aib(int poz,int val)
{
    for(int i=poz;i<=n;i+= (i&-i))
        aib[i]+=val;
}
ll sum(int poz)
{
    ll s=0;
    for(int i=poz;i>0;i-= (i & -i))
        s+=aib[i];
    return s;
}
struct quer
{
    int x,y,P;
}q[N];
bool comp(quer X,quer Y)
{
    if(X.y==Y.y)
        return X.x<Y.x;
    return X.y<Y.y;
}
int main()
{
    f>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
        update_aib(i,a[i]);
    }
    for(int i=1;i<=m;i++)
        f>>q[i].x>>q[i].y,q[i].P=i;
    sort(q+1,q+m+1,comp);
    int nr=1;
    for(int i=1;i<=m;i++)
    {
        while(nr<=q[i].y)
        {
            if(ult[a[nr]])
                update_aib(ult[a[nr]],-a[nr]);
            ult[a[nr]]=nr;
            nr++;
        }
        RE[q[i].P]=(sum(q[i].y)-sum(q[i].x-1))%MOD;
    }
    for(int i=1;i<=m;i++)
        g<<RE[i]<<'\n';
    return 0;
}