#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cctype>

using namespace std;

const int MOD = 666013;

struct Q {
  int l, r, index;
};

class Reader {
public:

  Reader (const char *name) {
    inp = fopen (name, "r");
    buff = new char [4096];
    cursor = 4096;
  }

  Reader &operator >> (int &n) {

    char c = GetChar ();
    while (not isdigit (c)) {
      c = GetChar ();
    }

    n = 0;
    while (isdigit (c)) {
      n = n * 10 + c - '0';
      c = GetChar ();
    }

    return (*this);
  }

private:

  FILE *inp;
  char *buff;
  int cursor;

  char GetChar () {

    if (cursor == 4096) {
      fread (buff, 1, 4096, inp);
      cursor = 0;
    }
    return buff[cursor ++];
  }
};

class Writer {
public:

  Writer (const char *name) {
    out = fopen (name, "w");
    buff = new char [4096];
    cursor = 0;
  }

  ~Writer () {
    fwrite (buff, 1, cursor, out);
  }

  Writer &operator << (long long n) {
    
    if (n < 10) {
      WriteChar (n + '0');
    }
    else {
      (*this) << (n / 10);
      WriteChar (n % 10 + '0');
    }
    return (*this);
  }

  Writer &operator << (char c) {
    WriteChar (c);
    return (*this);
  }

private:

  FILE *out;
  char *buff;
  int cursor;

  char WriteChar (char c) {

    if (cursor == 4096) {
      fwrite (buff, 1, 4096, out);
      cursor = 0;
    }
    buff[cursor ++] = c;
  }
};

void ExtendRR (int &r, int targetR, vector < int > &v, vector < int > &frecv, long long &sum) {

  while (r < targetR) {
    ++ r;
    if (++ frecv[v[r]] == 1) {
      sum += v[r];
    }
  }
}

void ExtendRL (int &r, int targetR, vector < int > &v, vector < int > &frecv, long long &sum) {

  while (r > targetR) {
    if (-- frecv[v[r]] == 0) {
      sum -= v[r];
    }
    -- r;
  }
}

void ExtendLR (int &l, int targetL, vector < int > &v, vector < int > &frecv, long long &sum) {

  while (l < targetL) {
    if (-- frecv[v[l]] == 0) {
      sum -= v[l];
    }
    ++ l;
  }
}

void ExtendLL (int &l, int targetL, vector < int > &v, vector < int > &frecv, long long &sum) {

  while (l > targetL) {
    -- l;
    if (++ frecv[v[l]] == 1) {
      sum += v[l];
    }
  }
}

int main () {
  
  Reader cin ("distincte.in");
  Writer cout ("distincte.out");

  int n, k, m;
  cin >> n >> k >> m;

  vector < int > v (n + 1);
  vector < int > frecv (k + 1);
  
  for (int i = 1; i <= n; ++ i) {
    cin >> v[i];
  }

  vector < Q > q (m + 1);
  vector < long long > ans (m + 1);
  for (int i = 1; i <= m; ++ i) {
    cin >> q[i].l >> q[i].r;
    q[i].index = i;
  }
  
  int sq = sqrt (n);
  sort (q.begin () + 1, q.end (), [&sq] (Q a, Q b) -> bool { 
    int la = (a.r - a.l) / sq;
    int lb = (b.r - b.l) / sq;
    if (la != lb) {
      return la < lb;
    }
    return a.r < b.r;
  });

  long long sum = 0;
  int left_end = 1, right_end = 0;
    
  for (int i = 1; i <= m; ++ i) {
   
    if (left_end > q[i].l) {
      ExtendLL (left_end, q[i].l, v, frecv, sum);
    }
    else if (left_end < q[i].l) {
      ExtendLR (left_end, q[i].l, v, frecv, sum);
    }

    if (right_end > q[i].r) {
      ExtendRL (right_end, q[i].r, v, frecv, sum);
    }
    else if (right_end < q[i].r) {
      ExtendRR (right_end, q[i].r, v, frecv, sum);
    }

    ans[q[i].index] = sum;
  }

  for (int i = 1; i <= m; ++ i) {
    cout << (ans[i] % MOD) << '\n';
  }
}