#include <fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
#define int long long
int bucket;
struct skib
{
    int a,b,ind;
};
bool cmp(skib c,skib d)
{
    int val1=c.a/bucket;
    int val2=d.a/bucket;
    if(val1==val2)
    {
        val1=c.b/bucket;
        val2=d.b/bucket;
        return val1<val2;
    }
    return val1<val2;
}
int arr[100001];
skib query[100001];
int frec[100001];
int ans[100001];
signed main()
{
    int n,m,k;
    in>>n>>k>>m;
    bucket=sqrt(m);
    for(int i=1; i<=n; i++)
    {
        in>>arr[i];
    }
    for(int i=1; i<=m; i++)
    {
        in>>query[i].a>>query[i].b;
        query[i].ind=i;
    }
    sort(query+1,query+m+1,cmp);
    int l=query[1].a;
    int r=l-1;
    int sum=0;
    for(int i=1; i<=m; i++)
    {
        int val1=query[i].a;
        while(l<val1)
        {
            l++;
            frec[arr[l-1]]--;
            if (frec[arr[l-1]]==0)
            {
                sum-=arr[l-1];
            }
        }
        while(l>val1)
        {
            l--;
            frec[arr[l]]++;
            if(frec[arr[l]]==1)
            {
                sum+=arr[l];
            }
        }
        int val2=query[i].b;
        while(r<val2)
        {
            r++;
            frec[arr[r]]++;
            if(frec[arr[r]]==1)
            {
                sum+=arr[r];
            }
        }
        while(r>val2)
        {
            r--;
            frec[arr[r+1]]--;
            if(frec[arr[r+1]]==0)
            {
                sum-=arr[r+1];
            }
        }
        ans[query[i].ind]=sum;
    }
    for(int i=1; i<=m; i++)
    {
        out<<ans[i]%666013<<"\n";
    }
    return 0;
}