#include <fstream>
#include <vector>
#include <random>
#include <ctime>
#include <map>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
using pii = pair<int,int>;
const int nmax = 1e5 + 1;
const int mod = 666013;
int n , m , x , v[nmax] , y , ans[nmax];
vector <pii> qr[nmax];
map<int,int>pos;
mt19937 mt(time(nullptr));
struct treap
{
    int val , poz , sum , pri;
    treap *l,*r;
};
void init(treap *&root, int &val , int &poz)
{
    root->val = val;
    root->sum = val;
    root->poz = poz;
    root->pri = mt();
    root->l = root->r = NULL;
}
void fix(treap *&root)
{
    root->sum = root->val;
    if(root->l!=NULL)
    {
        root->sum += root->l->sum;
        root->sum %= mod;
    }
    if(root->r!=NULL)
    {
        root->sum += root->r->sum;
        root->sum %= mod;
    }
}
treap *mrg( treap *a , treap *b)
{
    if(a == NULL) return b;
    if(b == NULL) return a;
    if(a->pri < b->pri)
    {
        a->r = mrg(a->r,b);
        fix(a);
        return a;
    }
    else
    {
        b->l = mrg(a,b->l);
        fix(b);
        return b;
    }
}
pair<treap*,treap*>split(treap *root , int sp)
{
    if(root == NULL) return {NULL,NULL};
    if(root->poz <= sp)
    {
        pair<treap*,treap*>aux = split(root->r,sp);
        root->r = aux.first;
        fix(root);
        return {root,aux.second};
    }
    else
    {
        pair<treap*,treap*>aux = split(root->l,sp);
        root->l = aux.second;
        fix(root);
        return {aux.first,root};
    }
}
int binsrc(treap *root, int &ind)
{
    if(root==NULL) return 0;
    if(root->poz < ind)
    {
        return binsrc(root->r,ind);
    }
    else
    {
        int sum = root->sum;
        if(root->l!=NULL) sum -= root->l->sum;
        while(sum < 0) sum += mod;
        return (binsrc(root->l,ind) + sum)%mod;
    }
}
/*void afis(treap *root)
{
    if(root == NULL) return;
    afis(root->l);
    cout << root->val << ' ';
    afis(root->r);
}*/
int main()
{
    cin >> n >> x >> m;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> v[i];
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> x >> y;
        qr[y].push_back({x,i});
    }
    treap *og = new treap;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(i == 1)
        {
            pos[v[i]] = i;
            init(og,v[i],i);
        }
        else
        {
            if(!pos[v[i]]);
            else
            {
                pair<treap*,treap*>aux = split(og,pos[v[i]]-1);
                pair<treap*,treap*>sec = split(aux.second,pos[v[i]]);
                og = mrg(aux.first,sec.second);
            }
            pos[v[i]] = i;
            treap *asta = new treap;
            init(asta,v[i],i);
            og = mrg(og,asta);
        }
        for(auto it : qr[i])
        {
            ans[it.second] = binsrc(og,it.first);
        }
    }
    for(int i = 1 ; i <= m ; ++i) cout << ans[i] << '\n';
    return 0;
}