#include <bits/stdc++.h>

#define Nmax 100005
#define ll long long
#define MOD 666013
#define lsb(x) ((x ^ (x - 1)) & x)

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

int N, M, K;
int last[Nmax];
ll bit[Nmax];
vector < pair <int, int> > Q[Nmax];
int ans[Nmax];
int A[Nmax];

void update(int pos, int val)
{
    for(; pos <= N; pos += lsb(pos))
        bit[pos] += val;
}

ll query(int pos)
{
    ll ret = 0;
    for(; pos >= 1; pos -= lsb(pos))
        ret += bit[pos];
    return ret;
}

int main()
{
    fin >> N >> K >> M;
    for(int i = 1; i <= N; i++)
        fin >> A[i];
    for(int i = 1; i <= M; i++)
    {
        int le, ri;
        fin >> le >> ri;
        Q[ri].push_back(make_pair(le, i));
    }
    for(int i = 1; i <= N; i++)
    {
        if(last[A[i]] != 0)
            update(last[A[i]], -A[i]);
        update(i, A[i]);
        last[A[i]] = i;
        for(auto it : Q[i])
            ans[it.second] = (query(i) - query(it.first - 1)) % MOD;
    }
    for(int i = 1; i <= M; i++)
        fout << ans[i] << "\n";
    return 0;
}