#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100010,modul = 666013;
int n,k,m;
int nums[NMAX];
int nextn[NMAX];
map<pair<int,int>,int> bit;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
void updatey(int x , int y , int val){
    while (y <= n+4){
        if(bit.find({x,y})==bit.end())
            bit.insert({{x,y},0});
        bit[{x,y}] += val;
        y += (y & -y);
    }
}
void update(int x,int y,int val)
{
    while(x<=n)
    {
        updatey(x,y,val);
        x+=(x&-x);
    }
}
int calcy(int x,int y)
{
    int sum = 0;
    while(y>0)
    {
        if(bit.find({x,y})==bit.end())
            bit.insert({{x,y},0});
        sum=(sum+bit[{x,y}])%modul;
        y-=(y&-y);
    }
    return sum;
}
int calc(int x,int y)
{
    int sum = 0;
    while(x>0)
    {
        sum=(sum+calcy(x,y))%modul;
        x-=(x&-x);
    }
    return sum;
}
int main()
{
    fin>>n>>k>>m;
    for(int i = 1;i<=n;i++)
        fin>>nums[i];
    vector<int> nexts(n+1,n+1);
    fill(nextn,nextn+NMAX,n+1);
    for(int i = n;i>=1;i--)
    {
        if(nexts[nums[i]]!=n+1)
        {
            nextn[i] = nexts[nums[i]];
        }
        nexts[nums[i]] = i;
        update(i,nextn[i],nums[i]);
        fout<<i<<" "<<nextn[i]<<" "<<nums[i]<<'\n';
    }

    for(int i = 0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        fout<<calc(y,n+1)-calc(x,n+1)-calc(y,y)+calc(x,y)<<'\n';
    }
    return 0;
}