#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define nozerous(x) (x & -x)
#define MOD 666013
#define M_PI           3.14159265358979323846
#define EPS 0.00001
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = (1 << 30), NMAX(100005), MMAX(100005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;
using ll = long long;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
};
struct chestie{
    int st, dr, wh;
}q[NMAX];
int v[NMAX], last[NMAX], AIB[NMAX], rez[NMAX], n, k, m;
inline bool cmp(chestie a, chestie b){
    return a.dr < b.dr;
}
void update(int poz, int val){
    if(poz == 0)
        return;
    for(; poz <= n; poz += nozerous(poz))
        AIB[poz] = (AIB[poz] + val + MOD) % MOD;
}
int query(int poz){
    int rez = 0;
    for(; poz >= 1; poz -= nozerous(poz))
        rez = (rez + AIB[poz] + MOD) % MOD;
    return rez;
}
int main()
{
    BUNA("distincte");
    cin >> n >> k >> m;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 1; i <= m; ++i){
        cin >> q[i].st >> q[i].dr;
        q[i].wh = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int j = 1;
    for(int i = 1; i <= m; ++i){
        while(j <= q[i].dr){
            update(last[v[j]], -v[j]);
            update(j, v[j]);
            last[v[j]] = j;
            ++j;
        }
        rez[q[i].wh] = (query(q[i].dr) - query(q[i].st - 1) + MOD) % MOD;
    }
    for(int i = 1; i <= m; ++i)
        cout << rez[i] << '\n';
    PA();
}