#include <fstream>
#include <algorithm>
#define MOD 666013
using namespace std;
const int NMAX = 100005;
int aib[NMAX];
ifstream cin("distincte.in");
ofstream cout("distincte.out");
struct interval
{
    int first, second, poz;
}evenimente[NMAX];
bool cmp(interval x,interval y)
{
    return x.first<y.first||(x.first==y.first&&x.second<y.second);
}
int lastVisit[NMAX], v[NMAX];
int answer[NMAX];
int n, m, k;
int querry(int poz){
    int sum = 0;
    for(int i = poz; i >= 1; i -= i & (-i)){
        sum = (sum + aib[i]) % MOD;
    }
    return sum;
}
void update(int pos, int val){
    for(int i = pos; i <= n; i += i & (-i)){
        aib[i] = (aib[i] + MOD + val) % MOD;
    }
}
int main()
{
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i ++)
        cin >> v[i];
    for(int i = 1; i <= m; i ++){
        cin >> evenimente[i].second >> evenimente[i].first;
        evenimente[i].poz = i;
        }/// le am citit inversat pentru a le putea sorta
    sort(evenimente + 1, evenimente + m + 1, cmp);
    int last_poz = 1;/// ne folosim de ultima pozitie, deoarece avem vectorul de intervale sortate dupa ultima pozitie, si astfel putem sa calculam liniar
    for(int i = 1; i <= m; i ++){
        for(int j = last_poz; j <= evenimente[i].first; j ++){
            if(lastVisit[v[j]] != 0){
                update(lastVisit[v[j]], -v[j]);/// scapam de prima deoarece o data cu  a doua oara aparitie a nr,  prima  devine irelevanta
            }
            lastVisit[v[j]] = j;
            update(lastVisit[v[j]], v[j]);
        }
        last_poz = evenimente[i].first;
        answer[evenimente[i].poz] = querry(evenimente[i].first) - querry(evenimente[i].second - 1);
        if(answer[evenimente[i].poz] < 0)
            answer[evenimente[i].poz] += MOD;
    }
    for(int i = 1; i <= m; i ++){
        cout << answer[i] % MOD << '\n';
    }
    return 0;
}