#include <fstream>
#include <algorithm>
#define MOD 666013

using namespace std;

int x, y, val, m, n, k, i, a[100010], ans[100010], arb[800010], last[100010], sum, qp, arbp;

void update(int nod, int l, int r)
{
    if(l == r)
    {
        arb[nod] = val;
        return;
    }
    int m = (l+r)/2;
    if(x <= m) update(2*nod, l, m);
    if(x > m) update(2*nod+1, m+1, r);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
    if(arb[nod] >= MOD) arb[nod] -= MOD;
}

void query(int nod, int l, int r)
{
    if(l >= x and r <= y)
    {
        sum += arb[nod];
        if(sum >= MOD) sum -= MOD;
        return;
    }
    int m = (l+r)/2;
    if(x <= m) query(2*nod, l, m);
    if(y > m) query(2*nod+1, m+1, r);
}

struct point
{
    int x, y, val;
};
struct elem
{
    int x, y, p;
};

point P[100010];
elem Q[100010];

bool cmp(elem a, elem b)
{
    return a.y > b.y;
}

bool cmp2(point a, point b)
{
    return a.y > b.y;
}

bool cmp3(elem a, elem b)
{
    return a.p < b.p;
}

int main()
{
    ifstream fi("distincte.in");
    ofstream fo("distincte.out");
    fi >> n >> k >> m;
    for(i = 1; i <= n; i++)
    {
        fi >> a[i];
        P[i].x = i; P[i].val = a[i];
        P[last[a[i]]].y = i;
        last[a[i]] = i;
    }
    for(i = 1; i <= n; i++)
        if(!P[i].y) P[i].y = n+1;

    sort(P+1, P+n+1, cmp2);

    for(i = 1; i <= m; i++)
    {
        fi >> Q[i].x >> Q[i].y;
        Q[i].p = i;
    }
    sort(Q+1, Q+m+1, cmp);
    qp = 1; arbp = 1;
    for(i = n+1; i > 0; i--)
    {
        while(Q[qp].y >= i and qp <= m)
        {
            x = Q[qp].x; y = Q[qp].y;
            sum = 0;
            query(1, 1, n);
            ans[Q[qp].p] = sum;
            qp++;
        }
        while(P[arbp].y >= i and arbp <= n)
        {
            x = P[arbp].x; val = P[arbp].val;
            update(1, 1, n);
            arbp++;
        }
    }
    for(i = 1; i <= m; i++) fo << ans[i] << "\n";
    return 0;
}