#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MODULO 666013

using namespace std;

int v[100010];
int x[100010];
int ans[100010];

struct Query
{
    int l, r, pos, ans;
    Query(int _l, int _r, int _p) : l(_l), r(_r), pos(_p) {}
};

bool cmp(Query q1, Query q2)
{
    if(q1.l == q2.l)
        return q1.r < q2.r;
    return q1.l < q2.l;
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);

    int N, M, K;

    cin >> N >> K >> M;
    for(int i = 1; i <= N; ++i)
        cin >> x[i];

    vector<Query> queries;

    for(int i = 0; i < M; ++i)
    {
        int l, r;
        cin >> l >> r;
        queries.push_back(Query(l, r, i));
    }

    sort(queries.begin(), queries.end(), cmp);

    int sum = 0;

    int left = queries[0].l;
    int right = queries[0].r;

    for(int i = left; i <= right; ++i)
    {
        if(!v[x[i]])
        {
            sum += x[i];
            sum %= MODULO;
        }
        ++v[x[i]];
    }

    ans[queries[0].pos] = sum;

    for(int i = 1; i < queries.size(); ++i)
    {
        Query& q = queries[i];
        int newL = q.l;
        int newR = q.r;
        while(left < newL)
        {
            --v[x[left]];
            if(v[x[left]] == 0)
            {
                sum = ((sum + MODULO) - x[left]) % MODULO;
            }
            ++left;
        }
        while(right > newR)
        {
            --v[x[right]];
            if(v[x[right]] == 0)
            {
                sum = ((sum + MODULO) - x[right]) % MODULO;
            }
            --right;
        }

        while(right < newR)
        {
            ++right;
            ++v[x[right]];
            if(v[x[right]] == 1)
            {
                sum = (sum + x[right]) % MODULO;
            }
        }
        ans[q.pos] = sum;
    }

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

    return 0;
}