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

        return h1 ^ h2;
    }
};
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
	return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

};
unordered_map<pair<int,int>,int,pair_hash> bit;
InParser 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;
}