#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
struct query
{
    int st,poz;
};
vector <query> q[100001];
int n,k,m,i,j,st,dr,fr[100001],v[100001];
long long aib[100001],sol[100001];
void update (int i,int val)
{
    for (; i<=n; i+=(i&-i))
        aib[i]+=val;
}
long long query (int i)
{
    long long sol=0;
    for (; i>0; i-=(i&-i))
        sol+=aib[i];
    return sol;
}
int main()
{
    fin>>n>>k>>m;
    for (i=1; i<=n; i++)
        fin>>v[i];
    for (i=1; i<=m; i++)
    {
        fin>>st>>dr;
        q[dr].push_back ({st,i});
    }
    for (i=1; i<=n; i++)
    {
        if (fr[v[i]]!=0)
            update (fr[v[i]],-v[i]);
        update (i,v[i]);
        fr[v[i]]=i;
        for (j=0; j<q[i].size (); j++)
        {
            st=q[i][j].st;
            sol[q[i][j].poz]=query (i)-query (st-1);
        }
    }
    for (i=1; i<=m; i++)
        fout<<sol[i]%666013<<"\n";
    return 0;
}