#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");

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

    vector<pair<pair<int,int>,int>> sorted_things;
    for(int i = 0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        sorted_things.push_back({{x,y},i});
    }

    sort(sorted_things.begin(),sorted_things.end(),compare);
        int last = 0;
    for(int i = 0;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]);
        }
        fout<<(calc(sorted_things[i].first.second)-calc(sorted_things[i].first.first-1))%modul<<'\n';
    }

    return 0;
}