#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;
#define int ll
const int N = (int)1e5 + 7;
const int MOD = 666013;
int a[N], pos[N], aib[N];

void update(int x, int val) {
        for (int i = x; i < N; i += i & -i) {
                aib[i] += val;
        }
}

int query(int x) {
        int ret = 0;
        for (int i = x; i >= 1; i -= i & -i) {
                ret += aib[i];
        }
        return ret;
}

struct Query {
        int l;
        int r;
        int ind;
};

Query q[N];
int ret[N];

signed main() {
#ifdef INFOARENA
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        freopen("distincte.in", "r", stdin);
        freopen("distincte.out", "w", stdout);
#else
        FILE* stream;
        freopen_s(&stream, "input.txt", "r", stdin);
#endif
        int n, k, m;
        cin >> n >> k >> m;
        for (int i = 1; i <= n; i++) {
                cin >> a[i];
        }
        for (int i = 1; i <= m; i++) {
                cin >> q[i].l >> q[i].r;
                q[i].ind = i;
        }
        sort(q + 1, q + m + 1, [&](Query a, Query b) {
                return a.r < b.r;
        });
        int j = 1;
        for (int i = 1; i <= m; i++) {
                while (j <= q[i].r) {
                        update(j, a[j]);
                        if (pos[a[j]] != 0) {
                                update(pos[a[j]], -a[j]);
                        }
                        pos[a[j]] = j;
                        j++;
                }
                ret[q[i].ind] = query(q[i].r) - query(q[i].l - 1);
        }
        for (int i = 1; i <= m; i++) {
                cout << ret[i] % MOD << "\n";
        }
        return 0;
}