#include <bits/stdc++.h>
#define DIM 100001
#define MOD 666013

using namespace std;

ifstream fin("distincte.in");

ofstream fout("distincte.out");

int v[DIM], frequency[DIM], sol[DIM];

int n, Q, useless, i, block;

long long ret;

struct Query{

    int st, dr, idx;

    bool operator < (const Query x){

        if(st / block == x.st / block)

            return (dr < x.dr);

        return (st / block < x.st / block);

    }

};

Query q[DIM];

void Add(int idx){

    idx = v[idx];

    frequency[idx]++;

    if(frequency[idx] == 1)

        ret += idx;

    ret = (ret + MOD) % MOD;

}

void Remove(int idx){

    idx = v[idx];

    frequency[idx]--;

    if(frequency[idx] == 0)

        ret -= idx;

    ret = (ret + MOD) % MOD;

}

void SolveQueries(){

    int curr_L = 1, curr_R = 0;

    for(int i=1;i<=Q;i++){

        int L = q[i].st;

        int R = q[i].dr;

        while(curr_R < R)

            Add(++curr_R);

        while(curr_R > R)

            Remove(curr_R--);

        while(curr_L < L)

            Remove(curr_L++);

        while(curr_L > L)

            Add(--curr_L);

        sol[q[i].idx] = ret;

    }

}

int main(){

    fin >> n >> useless >> Q;

    block = sqrt(n);

    for(i=1;i<=n;i++)

        fin >> v[i];

    for(i=1;i<=Q;i++){

        fin >> q[i].st >> q[i].dr;

        q[i].idx = i;

    }

    sort(q + 1, q + Q + 1);

    SolveQueries();

    for(i=1;i<=Q;i++)

        fout << sol[i] << "\n";

}