#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_SIZE = 1e5 + 17;
const int MOD = 666013;

long long segmentTree[MAX_SIZE * 6];
long long answer[MAX_SIZE];

int arr[MAX_SIZE];
int previousIndex[MAX_SIZE];

vector<pair<int, int>> queries[MAX_SIZE];

void update(int node, int left, int right, int index, int value)
{
    if (left == right)
    {
        segmentTree[node] = value;
        return;
    }

    int mid = (left + right) / 2;

    if (index <= mid)
        update(node * 2, left, mid, index, value);
    else
        update(node * 2 + 1, mid + 1, right, index, value);

    segmentTree[node] = (segmentTree[node * 2] + segmentTree[node * 2 + 1]) % MOD;
}

long long query(int node, int left, int right, int queryLeft, int queryRight)
{
    if (queryLeft <= left && right <= queryRight)
    {
        return segmentTree[node];
    }

    int mid = (left + right) / 2;

    long long sum = 0;

    if (queryLeft <= mid)
        sum += query(node * 2, left, mid, queryLeft, queryRight);

    if (queryRight > mid)
        sum += query(node * 2 + 1, mid + 1, right, queryLeft, queryRight);

    return sum % MOD;
}

int main()
{
    int N, M, K;
    fin >> N >> K >> M;

    for (int i = 1; i <= N; i++)
        fin >> arr[i];

    for (int i = 1; i <= M; i++)
    {
        int left, right;
        fin >> left >> right;

        queries[right].push_back({ left, i });
    }

    for (int i = 1; i <= N; i++)
    {
        update(1, 1, N, i, arr[i]);

        if (previousIndex[arr[i]] != 0)
        {
            update(1, 1, N, previousIndex[arr[i]], 0);
        }

        previousIndex[arr[i]] = i;

        for (auto j : queries[i])
            answer[j.second] = query(1, 1, N, j.first, i);
    }

    for (int i = 1; i <= M; i++)
        cout << answer[i] << '\n';

    return 0;
}