#include <bits/stdc++.h>

using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const int N = 1e5+5;
const int MOD = 666013;
int v[N],ans[N],fn[N],n;
bool fr[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(int val, int k)
{
    while (k<=n)
    {
        fn[k] = (fn[k]+val)%MOD;
        k+=k&-k;
    }
}
int sum(int k)
{
    int 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];
    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 = 1;
    for (int i = 1; i<=m; i++)
    {
        while (dr<q[i].y)
        {
            dr++;
            if (!fr[v[dr]])
                add(v[dr],dr);
            fr[v[dr]] = 1;
        }
        ans[q[i].p] = (sum(dr)-sum(q[i].x-1)+MOD)%MOD;
    }
    for (int i = 1; i<=m; i++)
        out << ans[i] << "\n";
}