#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define str pair< int, pair<int, int> >
#define x first
#define y second.first
#define z second.second

#define Nmax 100005
#define mod 666013

int n, m, k;
int val[Nmax];
int rez[Nmax];
int ant[Nmax];
int seg[5*Nmax];
str q[Nmax];

void readdata()
{
     freopen("distincte.in", "r", stdin);
     freopen("distincte.out", "w", stdout);
     
     int i;
     
     scanf("%d %d %d", &n, &k, &m);
     for (i = 1; i <= n; ++i)
         scanf("%d", &val[i]);
     for (i = 1; i <= m; ++i)
     {
         scanf("%d %d", &q[i].y, &q[i].x);
         q[i].z = i;
     }
}

void update(int poz, int st, int dr, int a, int b, int val)
{
     if (a <= st && dr <= b)
     {
           seg[poz] += val;
           if (seg[poz] >= mod) seg[poz] -= mod;
           if (seg[poz] < 0) seg[poz] += mod;
           return;
     }
     int m = (st+dr)/2;
     
     if (a <= m) update(poz*2, st, m, a, b, val);
     if (b > m) update(poz*2+1, m+1, dr, a, b, val);
}

int query(int poz, int st, int dr, int a)
{
    int s = 0, m = (st+dr)/2;
    
    s = seg[poz];
    
    if (st == dr) return s;
    
    if (a <= m) s += query(poz*2, st, m, a);
    else s += query(poz*2+1, m+1, dr, a);
    
    if (s >= mod) s -= mod;
    
    return s;
}

void solve()
{
     int i, j;
     int s;
     
     sort(q+1, q+m+1);
     
     j = 1;
     for (i = 1; i <= n; ++i)
     {
         s = val[i];
         
         if (ant[s]) update(1, 1, n, 1, ant[s], -s);
         update(1, 1, n, 1, i, s);
         
         while (j <= m && q[j].x == i)
         {
               rez[ q[j].z ] = query(1, 1, n, q[j].y);
               ++j;
         }

         ant[s] = i;
     }
}

void writedata()
{
     int i;
     
     for (i = 1; i <= m; ++i)
         printf("%d\n", rez[i]);
}

int main()
{
    readdata();
    solve();
    writedata();
    return 0;
}