#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],fr[N],ans[N],rad,Sol;
struct query
{
    int x,y,p;
} q[N];
bool cmp(query a, query b)
{
    if(a.x / rad != b.x / rad) return a.x / rad < b.x / rad;
    return a.y < b.y;
}
void add(int i)
{
    fr[v[i]]++;
    if (fr[v[i]] == 1)
        Sol = (Sol+v[i])%MOD;
}
void rem(int i)
{
    fr[v[i]]--;
    if (!fr[v[i]])
        Sol = (Sol-v[i]+MOD)%MOD;
}

int main()
{
    int n,m,k;
    in >> n >> k >> m;
    for (int i = 1; i<=n; i++)
        in >> v[i];
    rad = sqrt(n);
    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 st = q[1].x, dr = q[1].y;
    for (int i = st; i<=dr; i++)
    {
        fr[v[i]]++;
        if (fr[v[i]] == 1)
            Sol = (Sol+v[i])%MOD;
    }
    ans[q[1].p] = Sol;
    for (int i = 2; i<=m; i++)
    {
        while (st>q[i].x)
        {
            st--;
            add(st);
        }
        while (st<q[i].x)
        {
            rem(st);
            st++;
        }
        while (dr>q[i].y)
        {
            rem(dr);
            dr--;
        }
        while (dr<q[i].y)
        {
            dr++;
            add(dr);
        }
        ans[q[i].p] = Sol;
    }
    for (int i = 1; i<=m; i++)
        out << ans[i] << "\n";

}