#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100010, modul = 666013;
int n,k,m;
int nums[NMAX];
int pos[NMAX];
int bit[2*NMAX];
ifstream fin("distincte.in");
ofstream fout("distincte.out");
pair<pair<int,int>,int> sorted_things[NMAX];

void update(int x,int val)
{
    while(x<=n)
    {
        bit[x]=(bit[x]%modul+val%modul)%modul;
        x+=(x&-x);
    }
}
int calc(int x)
{
    int sum = 0;
    while(x>0)
    {
        sum=(sum%modul+bit[x]%modul)%modul;
        x-=(x&-x);
    }
    return sum;
}
bool compare(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)
{
    return a.first.second<b.first.second;
}
int ans[NMAX];
int main()
{
    fin>>n>>k>>m;
    for(int i = 1;i<=n;i++)
        fin>>nums[i];

    for(int i = 1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        sorted_things[i] = {{x,y},i};
    }

    sort(sorted_things+1,sorted_things+m+1,compare);
        int last = 0;
    for(int i = 1;i<=m;i++)
    {
        while(last<sorted_things[i].first.second)
        {
            last++;
            if(pos[nums[last]])
                update(pos[nums[last]],-nums[last]);
            pos[nums[last]] = last;
            update(last,nums[last]);
        }
        ans[sorted_things[i].second] = (calc(sorted_things[i].first.second)%modul-calc(sorted_things[i].first.first-1)%modul)%modul;
    }
    for(int i = 1;i<=m;i++)
        fout<<ans[i]<<'\n';
    return 0;
}