#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int aib[100009], pw, n, v[100009], sol[100009], prv[100009];
const int mod=666013;
struct elem
{
    int st, dr, index;
}q[100009];
inline bool cmp(const elem &a,const elem &b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}
void update (int poz, int add)
{
    int i;
    for (i=poz; i<=n; i+=i&-i)
        aib[i]+=add;
}
int query (int poz)
{
    int sol=0, i;
    for (i=poz; i>=1; i-=i&-i)
        sol+=aib[i];
    return sol;
}
signed main ()
{
    int m, k;
    f >> n >>k >> m;
    for (int i=1; i<=n; i++)
    {
        f >> v[i];
        update (i, v[i]);
    }
    for (int i=1; i<=m; i++)
    {
        f >> q[i].st >> q[i].dr;
        q[i].index=i;
    }
    sort (q+1, q+m+1, cmp);
    int i=1;
    for (int j=1; j<=m; j++)
    {
        while (i<=q[j].dr)
        {
            if (prv[v[i]])
            {
                update (prv[v[i]], -v[i]);
            }
            prv[v[i]]=v[i];
            i++;
        }
        sol[q[j].index]=(query (q[j].dr)%mod-query(q[j].st-1)%mod+mod)%mod;
    }
    for (int i=1; i<=m; i++)
        g << sol[i] %mod << '\n';
}