#include <fstream>
#include <vector>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
using pii = pair<int,int>;
const int nmax = 1e5 + 1;
int n , m , k , v[nmax] , l , r , last[nmax] , ans[nmax];
vector <pii> q[nmax];
class jaxana{
private:
    int bit[nmax];
public:
    jaxana(){for(int i = 1 ; i <= n ; ++i)bit[i] = 0;}
    void upd(int x , int v){
        for(int i = x ; i <= n ; i += i&-i)bit[i] = (bit[i]+v)%666013;
    }
    int qry(int x){
        int s = 0;
        for(int i = x ; i > 0 ; i -= i&-i) s=(s+666013+bit[i])%666013;
        return s;
    }
};
signed main()
{
    jaxana tree = jaxana();
    cin >> n >> k >> m;
    for(int i = 1 ; i <= n ; ++i) cin >> v[i];
    for(int i = 1 ; i <= m ; ++i)
        cin >> l >> r , q[l].push_back(make_pair(r,i));
    for(int i = n ; i >= 1 ; --i){
        if(last[v[i]]) tree.upd(last[v[i]],666013-v[i]);
        tree.upd(i,v[i]) , last[v[i]] = i;
        for(auto it : q[i]) ans[it.second] = tree.qry(it.first);
    }
    for(int i = 1 ; i <= m ; ++i) cout << ans[i] << '\n';
    return 0;
}