#include<fstream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<climits>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#define lsb(x) (x & (-x))
using namespace std;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

vector<long long>aib;

void aibup(int k,int vl){
  for(int i=k;i<aib.size();i+=lsb(i))aib[i]+=vl;
}
long long aibsum(int x){
 long long s=0;
 for(int i=x;i>0;i-=lsb(i))s+=aib[i];
 return s;
}

struct intr{
  int st,dr,nr;
};
bool cmp(intr a,intr b){
  return a.dr<b.dr;
}
int main()
{
 int n,k,m;
 cin>>n>>k>>m;
 vector<int>v(n+1);
 for(int i=1;i<=n;i++)cin>>v[i];
 vector<intr>q(m+1);
 for(int i=1;i<=m;i++){
    cin>>q[i].st>>q[i].dr;
    q[i].nr=i;
 }
 sort(q.begin()+1,q.end(),cmp);
 aib.resize(n+1,0);
 vector<int>ult(k+1,0);
 vector<long long>ans(m+1,0);
 int poz=0;
 for(int i=1;i<=m;i++){
    int st=q[i].st;
    int dr=q[i].dr;
    while(poz<dr){
        poz++;
        int x=v[poz];
        if(ult[x]!=0)aibup(ult[x],-x);
        aibup(poz,x);
        ult[x]=poz;
    }
    ans[q[i].nr]=(aibsum(dr)-aibsum(st-1)+666013)%666013;
 }
 for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
 return 0;
}