#include<fstream>
#include<vector>
using namespace std;

struct cell
{
    int st,ind;
};

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int modulo=666013;
const int NMAX=100005;

int n,m,k;
int poz[NMAX],a[NMAX],AIB[NMAX];
long long sol[NMAX];
vector<cell>v[NMAX];
vector<cell>::iterator it;

inline int zeros(int x)
{
    return x^(x&(x-1));
}

inline void UPDATE(int x,int val)
{
    for (int i=x;i>=1;i-=zeros(i))
        AIB[i]+=val;
}

inline long long Compute(int x)
{
    int i;
    long long rez=0;
    for (i=x;i<=n;i+=zeros(i)) rez+=AIB[i];
    return rez;
}

inline void SOLVE()
{
    int i;
    cell ca;
    for (i=1;i<=n;i++)
        {
            UPDATE(i,a[i]);
            if (poz[a[i]]) UPDATE(poz[a[i]],-a[i]);
            poz[a[i]]=i;
            for (it=v[i].begin();it!=v[i].end();it++)
                {
                    ca=*it;
                    sol[ca.ind]=Compute(ca.st);
                }
        }
    for (i=1;i<=m;i++)
        {
            sol[i]%=modulo;
            fout<<sol[i]<<"\n";
        }
}

int main()
{
    int i,x,y;
    cell ca;
    fin>>n>>k>>m;
    for (i=1;i<=n;i++) fin>>a[i];
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            ca.ind=i;
            ca.st=x;
            v[y].push_back(ca);
        }
    SOLVE();
    return 0;
}