#include <bits/stdc++.h>
#define NMAX 100003
#define MOD 666013
#define lsb(x) x&(-x)
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int N, M, K, X, Y;
long long BoB [NMAX];
vector < pair <int, int> > Q [NMAX];
int Ans [NMAX], V [NMAX], Pre [NMAX];
void UP (int pos, int val){
    for (; pos <= N; pos += lsb (pos))
        BoB [pos] += val;
}
long long QU (int pos){
    long long ret = 0;
    for (; pos >= 1; pos -= lsb (pos))
        ret += BoB [pos];
    return ret;
}
int main (){
    fin >> N >> K >> M;
    for (int i = 1; i <= N; i ++)
        fin >> V [i];
    for (int i = 1; i <= M; i ++){
        fin >> X >> Y;
        Q [Y].push_back (make_pair (X, i));
    }
    for (int i = 1; i <= N; i ++){
        if (Pre [V [i]])
            UP (Pre [V [i]], -V [i]);
        UP (i, V [i]); Pre [V [i]] = i;
        for (auto it : Q [i])
            Ans [it.second] = (QU (i) - QU (it.first - 1)) % MOD;
    }
    for (int i = 1; i <= M; i ++)
        fout << Ans [i] << '\n';
    return 0;
}