#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
 
constexpr int mod = 666013;
 
void mod_add(int& x, const int y){
    x += y;
    if(x >= mod){
        x -= mod; } }
     
int norm(const int x){
    if(x < 0){
        return x+mod; }
    return x; }
 
class aib{
    int n;
    vector<int> buf;
public:
    aib(const int N): n(N), buf(n+1, 0){}
    void update(int p, const int d){
        for(++p; p <= n; p += p&-p){
            mod_add(buf[p], d); } }
    int query(int p){
        int rez = 0;
        for(++p; p > 0; p -= p&-p){
            mod_add(rez, buf[p]); }
        return rez; }
    int query(int st, int dr){
        return norm(query(dr) - query(st-1)); } };
 
int main(){
    ifstream f("distincte.in");
    ofstream g("distincte.out");
 
    int n, k, m;
    f >> n >> k >> m;
 
    vector<int> v(n);
    for(auto& x : v){
        f >> x;
        --x; }
 
    struct query{ int st, ind; };
 
    vector<int> rez(m);
    vector<vector<query>> qs(n);
    for(int i = 0, st, dr; i < m; ++i){
        f >> st >> dr;
        qs[dr-1].push_back((query){st-1, i}); }
 
	vector<int> prev(k, -1);
    aib a(n);
 
    for(int dr = 0; dr < n; ++dr){
		a.update(dr, v[dr]+1);
		if(prev[v[dr]] > -1){
			a.update(prev[v[dr]], -v[dr]-1); }
		prev[v[dr]] = dr;
        for(const auto q : qs[dr]){
            rez[q.ind] = a.query(q.st, dr); } }
 
    for(const auto x : rez){
        g << x << '\n'; }
    return 0; }