#include <bits/stdc++.h>

using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const int N = 1e5+5;
const int MOD = 666013;
long long v[N],ans[N],fn[N]
int n,poz[N];
struct query
{
    int x,y,p;
} q[N];
bool cmp(query a, query b)
{
    if (a.y == b.y)
        return a.x<b.x;
    return a.y<b.y;
}
void add(long long val, int k)
{
    while (k<=n)
    {
        fn[k] = (fn[k]+val)%MOD;
        k+=k&-k;
    }
}
long long sum(int k)
{
    long long s = 0;
    while (k>0)
    {
        s = (s+fn[k])%MOD;
        k-=k&-k;
    }
    return s;
}
int main()
{
    int m,k;
    in >> n >> k >> m;
    for (int i = 1; i<=n; i++)
    {
        in >> v[i];
        add(v[i],i);
    }
    for (int i = 1; i<=m; i++)
        in >> q[i].x >> q[i].y, q[i].p = i;
    sort(q+1,q+m+1,cmp);
    int dr = 0;
    for (int i = 1; i<=m; i++)
    {
        while (dr<q[i].y)
        {
            dr++;
            if (poz[v[dr]])
                add(-v[dr],poz[v[dr]]);
            poz[v[dr]] = dr;
        }
        ans[q[i].p] = (sum(dr)-sum(q[i].x-1)+MOD)%MOD;
    }
    for (int i = 1; i<=m; i++)
        out << ans[i] << "\n";
}