#include <bits/stdc++.h>

using namespace std;

const int N = 100001;

long long fen[N];
int last[N];

struct Query
{
    int i, id;
};

vector<Query> q[N];
long long ans[N];

void update(int i, long long add)
{
    while(i < N)
    {
        fen[i] += add;
        i += (i & (-i));
    }
}

long long sum(int i)
{
    long long s = 0;

    while(i)
    {
        s += fen[i];
        i -= (i & (-i));
    }

    return s;
}

int main()
{
    int n, k, m;
    cin >> n >> k >> m;

    vector<int> a(n + 1);

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    // Read queries
    for(int x = 0; x < m; x++)
    {
        int i, j;
        cin >> i >> j;

        q[j].push_back({i, x});
    }

    // Go through the array
    for(int j = 1; j <= n; j++)
    {
        int x = a[j];

        // x appeared before -> remove old occurrence
        if(last[x])
            update(last[x], -x);

        // Add current occurrence
        update(j, x);

        last[x] = j;

        // Answer queries ending at j
        for(auto query : q[j])
        {
            int i = query.i;
            int id = query.id;

            ans[id] = sum(j) - sum(i - 1);
            ans[id] %= 666013;
        }
    }

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