#include <fstream>
#include<algorithm>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
 
struct cer
{
    int pozin, st, dr;
};
 
const int mod = 666013, nmax = 100005;
int vrasp[nmax], aib[nmax], poz[nmax], v[nmax], n, k, m;
cer query[nmax];
 
int zeros(int x)
{
    return (x ^ (x - 1)) & x;
}
 
void add(int x, int val)
{
    for(int i = x; i<=n; i += zeros(i))
        aib[i]=(aib[i] + val + mod)%mod;
}
 
int calc(int x)
{
    int rez = 0;
    for(int i = x; i; i -= zeros(i))
        rez = (rez + aib[i])%mod;
    return rez;
}
 
bool compar(cer x, cer y)
{
	return x.dr<y.dr;
}
 
int main()
{
    int player_unu=0;
 
    in>>n>>k>>m;
 
    for(int i = 1; i<=n; i++)
        in>>v[i];
 
    for(int i = 1; i<=m; i++)
    {
        in>>query[i].st>>query[i].dr;
		query[i].pozin = i;
    }
 
    sort(query + 1,query + m + 1, compar);
 
    for(int i = 1; i<=m; i++)
    {
		for(int j = query[i - 1].dr + 1; j<=query[i].dr; j++)
        {
            if(poz[v[j]])
            {
                add(poz[v[j]], -v[j]);
            }
            add(j, v[j]);
            poz[v[j]] = j;
        }
 
		vrasp[query[i].pozin] = (calc(query[i].dr) - calc(query[i].st - 1)  + mod)%mod;
    }
 
    for(int i = 1; i<=m; i++)
        out<<vrasp[i]<<'\n';
 
    return player_unu;
}