#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
 
const int MOD = 666013,Dim =  100005;
int aib[Dim],v[Dim],ans[Dim],pas[Dim],f[Dim],a[Dim];
int n,m,p;

struct idk{
    int x,y;
};
  
vector< idk >q[Dim];
int querry(int poz);
void update(int poz, int val);

int main()
{
    fin >> n >> m >> p;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        a[i] = f[v[i]];
        pas[a[i]] = i;
        if(a[i] == 0)
            update(i,v[i]);
        f[v[i]] = i;
    }
    for (int i=1;i<=p;++i){
        int x,y;
        fin >> x >> y;
        q[x].push_back({y,i});
    }
 
    for (int i = 1;i <=n; ++i) {
        if(i != 1 and pas[i-1] != 0)
            update(pas[i-1],v[pas[i-1]]);
        for (auto j : q[i])
            ans[j.y]=(querry(j.x)-querry(i-1)+MOD)%MOD;
    }
    for (int i = 1;i <= p; ++i)
        fout << ans[i] << "\n";
    return 0;
}


void update(int poz, int val)
{
    while(poz <= n)  {
        aib[poz]=(aib[poz] + val)%MOD;
        poz+=(poz&(-poz));
    }
}
 
int querry(int poz)
{
    int sum = 0;
    while(poz) {
        sum=(sum + aib[poz])%MOD;
        poz-=(poz&(-poz));
    }
    return sum;
}