#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
const int MOD = 666013;
const int Nmax = 1e5 + 1;
int v[Nmax], tree[4 * Nmax], ap[Nmax];
pair<pair<int, int>, int> querys[Nmax];
int n, k, m, start, fin, pos, nr = 1, ans, val;
vector<int> res;
void update(int node, int left, int right)
{
    if(left == right)
    {
        tree[node] = val;
        return;
    }
    int mij = (left + right) / 2;
    if(pos <= mij)
        update(2 * node, left, mij);
    else
        update(2 * node + 1, mij + 1, right);
    tree[node] = (tree[2 * node] + tree[2 * node + 1]) % MOD;
}
void query(int node, int left, int right)
{
    if(start <= left && right <= fin)
    {
        ans = (ans + tree[node]) % MOD;
        return;
    }
    int mij = (left + right) / 2;
    if(start <= mij)
        query(2 * node, left, mij);
    if(mij < fin)
        query(2 * node + 1, mij + 1, right);
}
int main()
{
    cin >> n >> k >> m;
    res.resize(m + 1);
    for(int i=1; i<=n; i++)
        cin >> v[i];
    for(int i=1; i<=m; i++)
    {
        querys[i].second = i;
        cin >> querys[i].first.first >> querys[i].first.second;
    }
    sort(querys + 1, querys + m + 1);
    for(int i=1; i<=n; i++)
    {
        if(ap[v[i]])
        {
            val = 0;
            pos = ap[v[i]];
            update(1, 1, n);
        }
        ap[v[i]] = i;
        val = v[i];
        pos = i;
        update(1, 1, n);
        //cout << tree[1] << " ";
        while(querys[nr].first.second == i)
        {
            start = querys[nr].first.first;
            fin = querys[nr].first.second;
            ans = 0;
            query(1 ,1 , n);
            res[querys[nr].second] = ans;
            nr++;
        }
    }
    for(int i=1; i<=m; i++)
        cout << res[i] << '\n';
    return 0;
}