#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 100000
#define MOD 666013
using namespace std;

struct Query {
   int left, right, pos;
};

Query Q[MAXN + 5];
int AIB[MAXN + 5], N, v[MAXN + 5], ans[MAXN + 5], loc[MAXN + 5];

void update(int pos, int val) {
   while(pos <= N) {
      AIB[pos] += val;
      AIB[pos] %= MOD;
      pos += (pos & (-pos));
   }
}

int query(int pos){
   int ans = 0;
   while(pos > 0) {
      ans += AIB[pos];
      ans %= MOD;
      pos -= (pos & (-pos));
   }
   return ans;
}

bool cmp (Query a, Query b) {
   if(a.right == b.right)
      return a.left < b.left;
   return a.right < b.right;
}

int main()
{
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");
    int K, M;
    cin >> N >> K >> M;
    for(int i = 1; i <= N; ++i) {
      cin >> v[i];
      update(i, v[i]);
    }
    for(int i = 1; i <= M; ++i) {
      cin >> Q[i].left >> Q[i].right;
      Q[i].pos = i;
    }
    sort(Q + 1, Q + M + 1, cmp);
    int p = 0;
    for(int i = 1; i <= M; ++i) {
      while(p < Q[i].right) {
         ++p;
         if(loc[v[p]]) {
            update(loc[v[p]], -v[p]);
         }
         loc[v[p]] = p;
      }
      ans[Q[i].pos] = query(Q[i].right) - query(Q[i].left - 1);
    }
    for(int i = 1; i <= M; ++i) {
      cout << ans[i] % MOD << '\n';
    }
    return 0;
}