#include <fstream>
#include <algorithm>
#define mod 666013
using namespace std;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

struct cv
{
    int st,dr,poz;
}q[100005];

long long n,k,m,v[100005],aib[100005],aparitie[100005],sol[100005];

void update(int p, int val)
{
    for(;p<=n; p+=(p&-p))
        aib[p]+=val;
}
long long query(int p)
{
    long long sum=0;
    for(; p>0; p-=(p&-p))
        sum+=aib[p];
    return sum;
}
bool cmp(cv a, cv b)
{
    return a.dr<b.dr;
}
int main()
{
    cin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    for(int i=1; i<=m; i++)
    {
        cin>>q[i].st>>q[i].dr;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    int j=0;
    for(int i=1; i<=m; i++)
    {
        while(j<q[i].dr)
        {
            j++;
            if(aparitie[v[j]])
                update(aparitie[v[j]],-v[j]);
            aparitie[v[j]]=j;
            update(j,v[j]);
        }
        sol[q[i].poz]=(query(q[i].dr)-query(q[i].st-1)+mod)%mod;
    }
    for(int i=1; i<=m;i++)
        cout<<sol[i]<<" ";
}