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

const int MOD = 666013;

std::vector<int> computeDistinctSums(const std::vector<int>& arr, const std::vector<std::pair<int, int>>& queries, int K) {
    std::vector<int> frequency(K + 1, 0);  // Vector de frecvete initializat cu 0
    std::vector<int> prefixSum(arr.size() + 1, 0);  // Vectorul sumelor prefix

    // Calcularea sumelor prefix
    for (int i = 1; i <= arr.size(); ++i) {
        prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
    }

    std::vector<int> distinctSums;  // Vectorul rezultat cu sumele distincte

    // Parcurgerea fiecarei intrebari
    for (const auto& query : queries) {
        int left = query.first;
        int right = query.second;

        // Calcularea sumei distincte utilizând sumele prefix
        int distinctSum = (prefixSum[right] - prefixSum[left - 1] + MOD) % MOD;

        // Excluderea elementelor duplicate prin scaderea frecventei lor
        for (int i = left; i <= right; ++i) {
            if (frequency[arr[i - 1]] > 0) {
                distinctSum = (distinctSum - arr[i - 1] + MOD) % MOD;
            }
            frequency[arr[i - 1]]++;
        }

        // Actualizarea frecventei elementelor la 0
        for (int i = left; i <= right; ++i) {
            frequency[arr[i - 1]] = 0;
        }

        distinctSums.push_back(distinctSum);
    }

    return distinctSums;
}

int main() {
    std::ifstream inputFile("distincte.in");
    std::ofstream outputFile("distincte.out");

    int N, K, M;
    inputFile >> N >> K >> M;

    std::vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        inputFile >> arr[i];
    }

    std::vector<std::pair<int, int>> queries(M);
    for (int i = 0; i < M; ++i) {
        int left, right;
        inputFile >> left >> right;
        queries[i] = std::make_pair(left, right);
    }

    std::vector<int> distinctSums = computeDistinctSums(arr, queries, K);

    // Scrierea rezultatelor in fisierul de iesire
    for (const auto& sum : distinctSums) {
        std::cout << sum << "\n";
    }

    inputFile.close();
    outputFile.close();

    return 0;
}