#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 100005
#define Amax 262145
#define x second.first
#define y first
#define z second.second
#define mod 666013

int n, k, m, a, b, vl;
int sir[Nmax], p[Nmax], prev[Nmax], ai[Amax];
pair<int, pair<int, int> > inv[Nmax];

void citire()
{
    int i;
    
    scanf("%d %d %d", &n, &k, &m);
    
    for (i = 1; i <= n; ++i)
        scanf("%d", &sir[i]);
    
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d", &inv[i].x, &inv[i].y);
        inv[i].z = i;
    }
}

void update(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
    {
        ai[nod] += vl;
        
        if (ai[nod] >= mod)
            ai[nod] -= mod;
        if (ai[nod] < 0)
            ai[nod] += mod;
        return;
    }
    else
    {
        int mij = (st + dr) / 2;
        
        if (a <= mij)
            update(nod*2, st, mij);
        
        if (mij < b)
            update(nod*2+1, mij + 1, dr);
    }
}

int query(int nod, int st, int dr)
{
    int t = ai[nod];
    
    if (st == dr)
       return t;
    else
    {
        
        int mij = (st + dr) / 2;
        
        if (a <= mij)
            t += query(nod*2, st, mij);
        else
            t += query(nod*2+1, mij + 1, dr);
        
        if (t >= mod)
            t -= mod;
            return t;
    }
}

void solve()
{
    int i, ind, q;
    
    
    sort(inv + 1, inv + m + 1);
    
    ind = 1;
    for (i = 1; i <= n; ++i)
    {
        q = sir[i];
        
        if (prev[q])
        {
            a = 1;
            b = prev[q];
            vl = -q;
            update(1, 1, n);
        }
        
        a = 1;
        b = i;
        vl = q;
        
        update(1, 1, n);
         
        while (ind <= m && inv[ind].y == i)
        {
            a = inv[ind].x;
            p[ inv[ind].z ] = query(1, 1, n);
            ++ind;
        }

         prev[q] = i;
     }
     
    for (i = 1; i <= m; ++i)
        printf("%d\n", p[i]);
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    citire();
    solve();
    return 0;
}