#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]);

    q.push_back(QUERY(0,0,0));
    for(i = 1; i <= m; i++) {
        scanf("%d%d",&x,&y);
        q.push_back(QUERY(x,y,i));
    }

    sort(q.begin() + 1,q.end(),cmp());
    for(i = 1; i <= m; i++) {
        for(j = q[i - 1].y + 1; j <= q[i].y; j++) {
            if(vis[val[j]])
                update(vis[val[j]],-val[j]);
            vis[val[j]] = j;
            update(j,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;
}