#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

const int MOD = 666013,NMAX = 100000;
int n,ans[NMAX + 10],vis[NMAX + 10],val[NMAX + 10],aib[NMAX + 10];

struct QUERY {
    int x,y,ind;
    QUERY (int x, int y, int ind) {
        this -> x = x;
        this -> y = y;
        this -> ind = ind;
        }
    };

class cmp {
    public:
    bool operator () (QUERY a, QUERY b) {
        return a.y < b.y;
        }
    };

vector <QUERY> q;

void update (int pos, int val) {
    for(; pos <= n; pos += (pos & -pos))
        aib[pos] = (aib[pos] + val + MOD) % MOD;
}

int query (int pos) {
    int ans = 0;
    for(; pos; pos = pos - (pos & - pos))
        ans = (ans + aib[pos]) % MOD;
    return ans;
}

int main() {
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int i,j,x,y,k,m;
    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",&x,&y);
        q.push_back(QUERY(x,y,i));
    }

    sort(q.begin(),q.end(),cmp());

    for(i = 1; i <= q[0].y; i++)
        if(!vis[val[i]])
            vis[val[i]] = i,
            update(i,val[i]);
        else  {
            update(vis[val[i]],-val[i]);
            vis[val[i]] = i;
            update(i,val[i]);
        }
    ans[q[0].ind] = query(q[0].y) - query(q[0].x - 1);

    for(i = 1; i < m; i++) {
        for(j = q[i - 1].y + 1; j <= q[i].y; j++)
            if(!vis[val[j]])
                vis[val[j]] = j,
                update(j,val[j]);
            else {
                update(vis[val[j]],-val[j]);
                vis[val[j]] = j;
                update(i,val[j]);
            }
        ans[q[i].ind] = (query(q[i].y) - query(q[i].x - 1) + MOD) % MOD;
        }

    for(i = 1; i <= m; i++)
        printf("%d\n",ans[i]);
    return 0;
}