#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
///aproapeperm
ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct Interogare
{
    int x, y, ind, ras;
};

int N, M, K, r;
int a[100005], fr[100005];
Interogare b[100005];

bool Cmp1(Interogare A, Interogare B)
{
    if (A.x / r == B.x / r) return A.y < B.y;
    return A.x < B.x;
}
bool Cmp2(Interogare A, Interogare B)
{
    return A.ind < B.ind;
}

int main()
{
    int st, dr, sum, x, y;
    fin >> N >> K >> M;
    r = sqrt(N);
    for (int i = 1; i <= N; i++)
        fin >> a[i];
    for (int i = 1; i <= M; i++)
    {
        fin >> b[i].x >> b[i].y;
        b[i].ind = i;
    }
    sort(b + 1, b + M + 1, Cmp1);
    st = 1; dr = 0; sum = 0;
    for (int i = 1; i <= M; i++)
    {
        x = b[i].x; y = b[i].y;
        while (st < x)
        {
            //if (fr[a[st]] == 1) sum -= a[st];
            fr[a[st]]--;
            if (fr[a[st]] == 0) sum = (sum - a[st] + MOD) % MOD;
            st++;
        }
        while (st > x)
        {
            st--;
            //if (fr[a[st]] == 1) sum -= a[st];
            fr[a[st]]++;
            if (fr[a[st]] == 1) sum = (sum + a[st]) % MOD;
        }
        while (dr < y)
        {
            dr++;
            //if (fr[a[dr]] == 1) sum -= a[dr];
            fr[a[dr]]++;
            if (fr[a[dr]] == 1) sum = (sum + a[dr]) % MOD;
        }
        while (dr > y)
        {
            //if (fr[a[dr]] == 1) sum -= a[dr];
            fr[a[dr]]--;
            if (fr[a[dr]] == 0) sum = (sum - a[dr] + MOD) % MOD;
            dr--;
        }
        b[i].ras = sum;
    }
    sort(b + 1, b + M + 1, Cmp2);
    for (int i = 1; i <= M; i++)
        fout << b[i].ras << "\n";
    return 0;
}