#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
const int Nmax = 1e5+1;
const int MOD = 666013;
int n, m, k, x, start, fin, ap[Nmax], cnt = 1, pos, val, res[Nmax];
vector<int> aib, v;
pair<pair<int, int>, int> qry[Nmax];
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
    return a.first.second < b.first.second;
}
void update(int node, int val)
{
    for(; node <= n; node += node&(-node))
    {
        aib[node] += val;
        aib[node] += MOD;
        aib[node] %= MOD;
    }

}
int query(int node)
{
    int ans = 0;
    for(; node > 0; node -= node&(-node))
    {
        ans += aib[node];
        ans %= MOD;
    }

    return ans;
}
int main()
{
    cin >> n >> k >> m;
    v.resize(n+1);
    aib.resize(n+1);
    for(int i=1; i<=n; i++)
        cin >> v[i];
    for(int i=1; i<=m; i++)
    {
        cin >> start >> fin;
        qry[i] = {{start, fin}, i};
    }
    sort(qry + 1, qry + m + 1, cmp);
    for(int i=1; i<=n; i++)
    {
        if(ap[v[i]])
        {
            pos = ap[v[i]];
            val = -v[i];
            update(pos, val);
        }
        ap[v[i]] = i;
        pos = i;
        val = v[i];
        update(pos, val);
        while(qry[cnt].first.second == i)
        {
            start = qry[cnt].first.first;
            fin = qry[cnt].first.second;
            int ans = query(fin) - query(start - 1);
            res[qry[cnt].second] = ans;
            cnt++;
        }
    }
    for(int i=1; i<=m; i++)
        cout << res[i] << '\n';
    return 0;
}