#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 100000
#define MOD 666013
#define ll long long
#define f first
#define s second

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

ll n, k, m, nxt[NMAX+10], pr[NMAX+10], v[NMAX+10];
ll ans[NMAX+10], aib[NMAX+10];
vector <pair <ll, ll> > q[NMAX+10];

void update(ll poz, ll val)
{	while(poz <= n)
		{	aib[poz] += (ll)val;
			ll lastBit = poz & (-poz);
			poz += lastBit;
		}
}

ll query(ll poz)
{	ll ans = 0;
	while(poz)
		{	ans += aib[poz];
			ll lastBit = poz & (-poz);
			poz -= lastBit;
		}
	return ans;
}

int main()
{
	fin >> n >> k >> m;
	for(ll i=1; i<=n; i++)
		{	fin >> v[i];
			if(pr[v[i]])
				nxt[pr[v[i]]] = i;
			else
				update(i, v[i]);
			pr[v[i]] = i;
		}
	for(ll i=1; i<=m; i++)
		{	ll x, y;
			fin >> x >> y;
			q[x].push_back({y, i});
		}
	for(ll i=1; i<=n; i++)
		{	for(auto u : q[i])
				ans[u.s] = query(u.f);
			update(i, -v[i]);
			if(nxt[i])
				update(nxt[i], v[i]);
		}
	for(ll i=1; i<=m; i++)
		fout << ans[i] % MOD << '\n';
	return 0;
}