#include<bits/stdc++.h>

using namespace std;

struct coord
{
    int x, y, pos;
};

const int NMAX = 1e5 + 5, MOD = 666013;
int n, m, k, v[NMAX], arbint[4 * NMAX], frev[NMAX], ans[NMAX];
coord q[NMAX];

bool fcmp(coord a, coord b)
{
    return a.y < b.y;
}

void update(int idx, int st, int dr, int val, int poz)
{
    if(st == dr)
    {
        arbint[idx] = val; 
        return;
    }

    int mij = (st + dr) / 2;
    if(poz <= mij)
        update(idx * 2, st, mij, val, poz);
    else
        update(idx * 2 + 1, mij + 1, dr, val, poz);
    arbint[idx] = (arbint[idx * 2] + arbint[idx * 2 + 1]) % MOD;
}

int query(int idx, int st, int dr, int arbst, int arbdr)
{
    if(st > arbdr || dr < arbst)
        return 0;

    if(st >= arbst && dr <= arbdr)
        return arbint[idx];
    
    int mij = (st + dr) / 2;
    return (query(idx * 2, st, mij, arbst, arbdr) + query(idx * 2 + 1, mij + 1, dr, arbst, arbdr)) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);

    cin >> n >> m >> k;
    int x;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    
    int a, b;
    for(int i = 1; i <= k; i++)
    {
        cin >> a >> b;
        q[i] = {a, b, i};
    }

    sort(q + 1, q + k + 1, fcmp);

    int st = 1;
    for(int i = 1 ; i <= k; i++)
    {
        while(st <= q[i].y)
        {
            if(frev[v[st]])
                update(1, 1, n, 0, frev[v[st]]);
            update(1, 1, n, v[st], st);
            frev[v[st]] = st;
            st++;
        }
        
        ans[q[i].pos] = query(1, 1, n, q[i].x, q[i].y);
    }
    
    for(int i = 1; i <= k; i++)
        cout << ans[i] << "\n";
}