#define nume "distincte"
//#define DBG

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>

using namespace std;
using namespace __gnu_cxx;

//#define _PARSARE_
#ifdef _PARSARE_
#define DIM 8192
char ax[DIM+16];
int _idx;
template<class T>
inline void cit(T& x)
{
    x=0;
    while((ax[_idx]<'0' || ax[_idx]>'9') && (ax[_idx]!='-'))
        if(++_idx==DIM)fread(ax, 1, DIM, stdin), _idx=0;

    int neg=0;
    if(ax[_idx]=='-') {
        neg=1;
        if(++_idx==DIM)fread(ax, 1, DIM, stdin),_idx=0;
    }

    while(ax[_idx]>='0' && ax[_idx]<='9') {
        x=x*10+ax[_idx]-'0';
        if(++_idx==DIM)fread(ax,1, DIM, stdin),_idx=0;
    }
    if(neg) x=-x;
}
#else
#ifndef ONLINE_JUDGE
ifstream fin (nume ".in");
#endif
#endif //_PARSARE_
#ifndef ONLINE_JUDGE
ofstream fout(nume ".out");
#endif
#ifdef DBG
#define fout cout
#endif
//// hash-uri
//#include<ext/hash_map>
//hash_multimap<int,int> H;
//hash_map<char*,int> H;
//const double PI = acos(-1.0);
//const double EPS = 1e-9;
#define foreach(it, v) for (typeof((v).begin()) it = (v).begin(),stop=(v).end(); it != stop; ++it)
#define foreach_r(it, v) for (typeof((v).rbegin()) it = (v).rbegin(),stop=(v).rend(); it != stop; ++it)
template<class T> inline void Swap(T& a,T& b)
{
    a^=b,b^=a,a^=b;
}

int n,m,k;
int aib[100000+10];
int a[100000+10];
int next[100000+10];
int prev[100000+10];
const int MOD = 666013;
struct distincte {
    int p,i,j,r;
} q[100000+10],qq[100000+10];
vector<int> sol;

bool cmp(distincte a, distincte b)
{
    return a.j < b.j;
}

void update(int i, int val)
{
    for (int ii=i; ii <= n; ii+=(ii&-ii))
        aib[ii] = (aib[ii] + val)%MOD;
}
int query(int i)
{
    int sum = 0;
    for (int ii=i; ii; ii-=(ii&-ii))
        sum = (sum+aib[ii])%MOD;
    return sum;
}

int main()
{
#ifdef _PARSARE_
#ifndef ONLINE_JUDGE
    freopen(nume ".in","r",stdin);
#endif
    cit(n);
#endif

    fin>>n>>k>>m;

    for(int i=0; i<n; ++i) {
        fin>>a[i];
    }
    for(int i=0; i<m; ++i) {
        fin>>q[i].i>>q[i].j;
        q[i].p = i;
    }
    memcpy(qq,q,sizeof(q));
    sort(q,q+m,cmp);

    memset(next,0x3f,sizeof(next));
    memset(prev,0xff,sizeof(next));

    int st = 0, dr = n-1;
    for(int i=0; i<m; ++i) {
        for(; st < q[i].j; ++st) {
            update(st+1,a[st]);
            if(prev[a[st]] != -1)
                update(prev[a[st]]+1,-a[st]);
            prev[a[st]] = st;
        }
        qq[q[i].p].r = query(q[i].j) - query(q[i].i - 1);
    }
    for(int i=0; i<m; ++i) {
        fout<<qq[i].r<<'\n';
    }

#ifndef DBG
#ifndef ONLINE_JUDGE
    fout.close();
#endif
#endif
    return 0;
}