#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

int n,m,k;

int a[100005];

int l[100005],r[100005];

vector <int> h[100005];

int last[100005];

long long aib[100005];

void update(int p,int v)
{
    for(int i=p; i<=n; i+=(i&(-i)))
        aib[i]+=v;
}

long long query(int p)
{
    long long ans=0;
    for(int i=n; i>=1; i-=(i&(-i)))
        ans+=aib[i];
    for(int i=p-1; i>=1; i-=(i&(-i)))
        ans-=aib[i];
    return ans;
}

long long ans[100005];

int main()
{
    fin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        fin>>a[i];
    for(int i=1; i<=m; i++)
    {
        fin>>l[i]>>r[i];
        h[r[i]].push_back(i);
    }

    for(int i=1; i<=n; i++)
    {
        if(last[a[i]]>=1)
            update(last[a[i]],-a[i]);
        last[a[i]]=i;
        update(i,a[i]);

        for(int ind:h[i])
        {
            int j=l[ind];
            ans[ind]=query(j);
        }
    }

    for(int i=1; i<=m; i++)
        fout<<ans[i]%666013<<"\n";
    return 0;
}