#include <cstdio>
#include <algorithm>
#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 << (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;
  }
};

Q q[100007];
int v[100007], ans[100007], frecv[100007];

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

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

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

  for (int i = 1; i <= m; ++ i) {
    cin >> q[i].l >> q[i].r;
    q[i].index = i;
  }
  
  int sq = 0, st = 0, dr = n;
  while (st <= dr) {

    int mid = (st + dr) >> 1;
    if (1ll * mid * mid > n) {
      dr = mid - 1;
    }
    else {
      st = mid + 1;
      sq = mid;
    }
  }

  sort (q + 1, q + m + 1, [&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;
  });

  int sum = 0, left_end = 1, right_end = 0;
  for (int i = 1; i <= m; ++ i) {
    
    while (left_end < q[i].l) {
      if (-- frecv[v[left_end]] == 0) {
        sum -= v[left_end];
        if (sum < 0) {
          sum += MOD;
        }
      }
      ++ left_end;
    }

    while (left_end > q[i].l) {
      -- left_end;
      if (++ frecv[v[left_end]] == 1) {
        sum += v[left_end];
        if (sum >= MOD) {
          sum -= MOD;
        }
      }
    }

    while (right_end < q[i].r) {
      ++ right_end;
      if (++ frecv[v[right_end]] == 1) {
        sum += v[right_end];
        if (sum >= MOD) {
          sum -= MOD;
        }
      }
    }

    while (right_end > q[i].r) {
      if (-- frecv[v[right_end]] == 0) {
        sum -= v[right_end];
        if (sum < 0) {
          sum += MOD;
        }
      }
      -- right_end;
    }

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

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