#include <bits/stdc++.h>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define int long long
int n, aib[100001], k, m, v[100001], a, b, last[100001], rez[1000001];
vector<pair<int, int>> q[100001];
const int mod=666013;

void update(int poz, int val)
{
    while (poz<=n)
    {
        aib[poz]=aib[poz]+val;
        poz+=(poz&(-poz));
    }
}

int query(int a, int b)
{
    if (a!=1)
    {
        return query(1, b)-query(1, a-1);
    }
    int sumtot=0;
    while (b>0)
    {
        sumtot=sumtot+aib[b];
        b-=(b&(-b));
    }
    return sumtot;
}

signed main()
{
    fin>>n>>k>>m;
    for (int i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b;
        q[b].push_back({a, i});
    }
    for (int i=1; i<=n; i++)
    {
        if (last[v[i]]==0)
        {
            last[v[i]]=i;
            update(i, v[i]);//poz-val
        }
        else
        {
            update(last[v[i]], -v[i]);
            last[v[i]]=i;
            update(i, v[i]);
        }
        for(auto j: q[i])
        {
            rez[j.second]=query(j.first, i);
        }
    }
    for (int i=1; i<=m; i++)
    {
        fout<<rez[i]%mod<<'\n';
    }

    return 0;
}