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

using namespace std;

const int MOD = 666013;

struct Q {
  int l, 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 << (int 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;

  void WriteChar (char c) {

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

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

class Bit {
public:

  Bit () {
    
    cin >> n >> k >> m;

    val.resize (n + 1);
    tree.resize (n + 1);
    last.resize (n + 1);

    q.resize (n + 1);
    ans.resize (m + 1);

    for (int i = 1; i <= n; ++ i) {
      cin >> val[i];
    }

    for (int i = 1; i <= m; ++ i) {
      int l, r;
      cin >> l >> r;
      q[r].push_back ({l, i});
    }
  }

  void Solve () {

    for (int i = 1; i <= n; ++ i) {
        
      if (last[val[i]]) {
        Update (last[val[i]], -val[i]);
      }

      last[val[i]] = i;
      Update (i, val[i]);

      for (auto x : q[i]) {
        ans[x.index] = (Query (i) - Query (x.l - 1)) % MOD;
      }
    }

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

private:
  
  int n, m, k;
  vector < vector < Q > > q;
  vector < int >  tree, last, ans, val;
  
  long long Query (int poz) {

    long long sum = 0;
    while (poz) {
      sum += tree[poz];
      poz -= (poz & -poz);
    }
    return sum;
  }

  void Update (int poz, int val) {

    while (poz <= n) {
      tree[poz] += val;
      poz += (poz & -poz);
    }
  }
};

int main () {
  
  Bit B;
  B.Solve ();
}