#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int dim = 1e5 + 2, mod = 666013;
int n, i, m, k, v[dim], ultimul[dim], t[2 * dim], ans[dim];

struct range{
    int x, y, poz;
}q[dim];

void build()
{
    for(i = n - 1; i >= 1; i--)
        t[i] = (t[i * 2] + t[i * 2 + 1]) % mod;
}

void update(int p, int val)
{
    p += n - 1;
    t[p] = val % mod;

    while(p > 1)
    {
        t[p / 2] = (t[p] + t[p^1]) % mod;
        p = p / 2;
    }
}

int query(int st, int dr)
{
    int rez = 0;

    st = st + n - 1;
    dr = dr + n;

    while(st < dr)
    {
        //fout << "st = " << st << ", dr = " << dr << endl;
        if(st % 2 == 1)
        {
            rez = (rez + t[st]) % mod;
            //fout << "Adun t[" << st << "] = " << t[st] << endl;
            st++;
        }

        if(dr % 2 == 1)
        {
            dr--;
            rez = (rez + t[dr]) % mod;
            //fout << "Adun t[" << dr << "] = " << t[dr] << endl;
        }
        st = st / 2;
        dr = dr / 2;
    }

    return rez;
}

bool comparator1(range A, range B)
{
    return A.y < B.y;
}

int main()
{
    fin >> n >> k >> m;

    for(i = 1; i <= n; i++)
        fin >> v[i];

    for(i = 1; i <= m; i++)
    {
        fin >> q[i].x >> q[i].y;
        q[i].poz = i;
    }

    sort(q + 1, q + 1 + m, comparator1);

    int j = 1;

    for(i = 1; i <= n && j <= m; i++)
    {
        if(ultimul[v[i]] != 0)
            update(ultimul[v[i]], 0);

        update(i, v[i]);
        ultimul[v[i]] = i;
        if(i == q[j].y)
        {
            while(i == q[j].y && j <= m)
            {
                ans[q[j].poz] = query(q[j].x, q[j].y) % mod;
                j++;
            }
        }
    }

    for(i = 1; i <= m; i++)
        fout << ans[i] << '\n';
    return 0;
}