#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100010, modul = 666013;
int n,k,m;
int nums[NMAX];
int nextn[NMAX];
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;
    }
};

unordered_map<pair<int,int>,int,pair_hash> bit;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

void updatey(int x , int y , int val){
    while (y <= n+2){
        if(bit.find({x,y})==bit.end())
            bit.insert({{x,y},val});
        else
            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())
            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);
    for(int i = n;i>=1;i--)
    {
        nextn[i] = nexts[nums[i]];
        nexts[nums[i]] = i;
        update(i,nextn[i],nums[i]);
    }

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