#include <bits/stdc++.h>
using namespace std;

///----------TOGGLES
#define FIO
#define LONGER
//#define TESTS

///---------

#ifdef LONGER
    #define int long long
#endif // LONGER

#ifdef FIO
    const string fname="distincte";
    ifstream in(fname+".in");
    ofstream out(fname+".out");
    #define cin in
    #define cout out
#endif // FIO

///--------

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///-------STL++-----
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) x.size()
#define pb(x,y) x.push_back(y)
#define mp(x,y) make_pair(x,y)
#define fr(i,n) for(int i=1;i<=n;i++)
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pdd = pair<double, double>;
using veci = vector<int>;
using vecp = vector<pii>;
template<typename T> using PQ = priority_queue<T, vector<T>, greater<T> >;

///-----CODE GOES HERE-----

struct Arbint{
    veci arb;
    int offset;
    Arbint(int n) : offset(n){
        arb.assign(n*2+1,0);
    }
    void update(int poz, int val)
    {
        arb[poz+=offset-1]=val;
        for(poz>>=1;poz>0;poz>>=1) arb[poz]=arb[poz*2]+arb[poz*2+1];
    }
    int query(int st, int dr)
    {
        int ans=0;
        for(st+=offset-1, dr+=offset; st<dr; st>>=1, dr>>=1)
        {
            if(st&1) ans=ans+arb[st++];
            if(dr&1) ans=ans+arb[--dr];
        }
        return ans;
    }
};

const int maxn = 1e5+5;
const int mod = 666013;

int n,k,m;
int v[maxn], st[maxn], dr[maxn], ans[maxn];
int last[maxn];
int srt[maxn];
void solve()
{
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=m;i++) cin>>st[i]>>dr[i], srt[i]=i;
    sort(srt+1,srt+m+1, [&](int a, int b){return dr[a]<dr[b];});

    Arbint arb(n);

    int cap=0;
    for(int i=1;i<=m;i++)
    {
        int j=srt[i];
        while(cap<dr[j])
        {
            cap++;
            if(last[v[cap]]!=0) arb.update(last[v[cap]], 0);
            arb.update(cap, v[cap]);
            last[v[cap]]=cap;
        }
        ans[j]=arb.query(st[j],n);
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]%mod<<'\n';
    }
}

///---MAIN FUNC-------

int32_t main()
{
    IOS;
    int t=1;
    #ifdef TESTS
        cin>>t;
    #endif // TESTS
    while(t--)
    {
        solve();
    }
    return 0;
}