#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=100005;

struct query
{
    int x,y,p;
} q[N];

bool cmp(const query &a,const query &b)
{
    return a.y<b.y;
}

int n,m,k,v[N];
long long a[N],r[N],f[N];

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

long long suma(int p)
{
    long long s=0;
    for(int i=p; i>=1; i-=(i&(-i)))
{
    s+=r[i];
    }
    return s;
}

int main()
{
    int h=1;
    cin >> n >> k >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    for(int i=1; i<=m; i++)
    {
        cin >> q[i].x >> q[i].y;
        q[i].p=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1; i<=n; i++)
    {
        if(v[a[i]]!=0)
        {
            update(v[a[i]],-a[i]);
        }
        v[a[i]]=i;
        update(i,a[i]);
        while(h<=m && q[h].y==i)
        {
            f[q[h].p]=suma(q[h].y)-suma(q[h].x-1);
            h++;
        }
    }
    for(int i=1; i<=m; i++)
    {
        cout << f[i]%666013 << "\n";
    }
    return 0;
}