#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("distincte.in");
ofstream cout ("distincte.out");

const int MOD = 666013;

struct Query {
  int x, y, ind;
  bool operator < (const Query &other) const {
    return y < other.y;
  }
} q[100005];

int n, k, m;
int sol;

int ans[100005], v[100005], aib[100005], poz[100005];

int lsb(int n) {
  return n & -n;
}

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

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

int main() {
  cin >> n >> k >> m;
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  for(int i = 1; i <= m; i++) {
    cin >> q[i].x >> q[i].y;
    q[i].ind = i;
  }
  sort(q + 1, q + m + 1);
  int j = 0;
  for(int i = 1; i <= m; i++) {
    while(j < q[i].y) {
      j++;
      if(poz[v[j]])
        update(poz[v[j]], MOD - v[j]);
      poz[v[j]] = j;
      update(poz[v[j]], v[j]);
    }
    ans[q[i].ind] = (query(q[i].y) - query(q[i].x - 1) + MOD) % MOD;
  }
  for(int i = 1; i <= m; i++)
    cout << ans[i] << "\n";
  return 0;
}