// Aparent exista si un MOD...
// Cine ar fi crezut?
#include <bits/stdc++.h>
#define N_MAX 100000
#define lsb(i) ((i ^ (i - 1)) & i)
#define ll long long
#define MOD 666013

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

int N, K, M, v[N_MAX + 5];
vector <pair <int, pair <int, int> > > queries;

int last_pos[N_MAX + 5], pos = 0;
int bit[N_MAX + 5], answer[N_MAX + 5];

bool compare(pair <int, pair <int, int> > A, pair <int, pair <int, int> > B)
{
    if (A.second.second > B.second.second)
        return 0;
    if (A.second.second < B.second.second)
        return 1;
    if (A.second.first > B.second.first)
        return 0;
    return 1;
}

void update (int x, int val)
{
    for (int i = x; i <= N; i += lsb(i))
        bit[i] = (bit[i] + val + MOD) % MOD;
}

int query (int x)
{
    int ret = 0;
    for (int i = x; i >= 1; i -= lsb(i))
        ret = (ret + bit[i]) % MOD;
    return ret;
}

int main()
{
    fin >> N >> K >> M;
    for (int i = 1; i <= N; i++)
        fin >> v[i];
    for (int i = 1; i <= M; i++)
    {
        int st, dr;
        fin >> st >> dr;
        queries.push_back({i, {st, dr}});
    }
    sort(queries.begin(), queries.end(), compare);

    for (int i = 1; i <= N; i++)
    {
        update(i, v[i]);
        if (last_pos[v[i]])
            update(last_pos[v[i]], -v[i]);
        last_pos[v[i]] = i;
        int aux = query(i);
        while (pos < M && queries[pos].second.second == i)
        {
            answer[queries[pos].first] = (aux - query(queries[pos].second.first - 1) + MOD) % MOD;
            pos++;
        }
    }

    for (int i = 1; i <= M; i++)
        fout << answer[i] << "\n";
    return 0;
}