#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int MOD = 666013;

int block_size;

struct Query {
    int l, r, idx;
    bool operator < (const Query &E) const {
        if(l / block_size != E.l / block_size)
            return make_pair(l, r) < make_pair(E.l, E.r);
        return (l / block_size & 1)? (r < E.r) : (r > E.r);
    }
} q[100001];

int a[100001], F[100001], ans[100001];
int N, K, M;

void add_(int &a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
}

void dec_(int &a, int b) {
    a -= b;
    while(a < 0)
        a += MOD;
}

void solve() {
    cin >> N >> K >> M;

    block_size = sqrt(N);
    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].idx = i;

    sort(q + 1, q + M + 1);
    for(int i = 1, l = 1, r = 0, sum = 0;i <= M;i++) {
        while(l > q[i].l) {
            if(++F[a[--l]] == 1)
                add_(sum, a[l]);
        }

        while(l < q[i].l) {
            if(--F[a[l++]] == 0)
                dec_(sum, a[l - 1]);
        }

        while(r < q[i].r) {
            if(++F[a[++r]] == 1)
                add_(sum, a[r]);
        }

        while(r > q[i].r) {
            if(--F[a[r--]] == 0)
                dec_(sum, a[r + 1]);
        }

        ans[q[i].idx] = sum;
    }

    for(int i = 1;i <= M;i++)
        cout << ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("distincte");

    int T = 1;
    for(;T;T--) {
        solve();
    }

    return 0;
}