#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int MOD=666013;
struct Query
{
    int l,r,id;
    bool operator<(const Query& other)const
    {
        return r<other.r;
    }
};
struct AIB
{
    int sz;
    vector<long long> a;
    AIB(int N)
    {
        sz=N;
        a.assign(N+2,0);
    }
    void add(int idx,long long val)
    {
        for(;idx<=sz;idx+=idx&-idx)
        {
            a[idx]=(a[idx]+val+MOD)%MOD;
        }
    }
    long long query(int k)
    {
        long long sum=0;
        for(;k>0;k-=k&-k)
        {
            sum=(sum+a[k])%MOD;
        }
        return sum;
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N,K,M;
    fin>>N>>K>>M;
    vector<int> v(N+1);
    for(int i=1;i<=N;i++)
    {
        fin>>v[i];
    }
    vector<Query> queries(M);
    for(int i=0;i<M;i++)
    {
        fin>>queries[i].l>>queries[i].r;
        queries[i].id=i;
    }
    sort(queries.begin(),queries.end());
    AIB bit(N);
    vector<int> last_pos(K+1,0);
    vector<long long> rez(M);
    int current_r=0;
    for(int i=0;i<M;i++)
    {
        while(current_r<queries[i].r)
        {
            current_r++;
            int val=v[current_r];
            if(last_pos[val]!=0)
            {
                bit.add(last_pos[val],-val);
            }
            bit.add(current_r,val);
            last_pos[val]=current_r;
        }
        long long sum_r=bit.query(queries[i].r);
        long long sum_l=bit.query(queries[i].l-1);
        rez[queries[i].id]=(sum_r-sum_l+MOD)%MOD;
    }
    for(int i=0;i<M;i++)
    {
        fout<<rez[i]<<'\n';
    }

    return 0;
}