#include <fstream>
#include <algorithm>

#define MAX 131072
#define REST 666013

using namespace std;

int v[MAX], aib[MAX], last[MAX], sol[MAX], n, k, m, poz = 1;

struct query
{
    int l, r, ind;
}q[MAX];

bool cmp(query a, query b)
{
    return a.r < b.r;
}

void update(int val, int poz)
{
    for(; poz <= n; poz += poz & (-poz))
        aib[poz] = (aib[poz] + val + REST) % REST;
}

int query(int poz)
{
    int sum = 0;
    for(; poz; poz -= poz & (-poz))
        sum = (sum + aib[poz]) % REST;
    return sum;
}

int main()
{
    ifstream in("distincte.in");
    in>>n>>k>>m;
    for(int i = 1; i <= n; i++) in>>v[i];
    for(int i = 1; i <= m; i++)
    {
        q[i].ind = i;
        in>>q[i].l>>q[i].r;
    } in.close();
    sort(q + 1, q + m + 1, cmp);
    for(int i = 1; i <= m; i++)
    {
        while(poz <= q[i].r)
        {
            if(last[v[poz]])
                update(-v[poz], last[v[poz]]);
            update(v[poz], poz);
            last[v[poz]] = poz;
            poz++;
        }
        sol[q[i].ind] = query(q[i].r) - query(q[i].l - 1);
    }
    ofstream out("distincte.out");
    for(int i = 1; i <= m; i++)
        out<<(sol[i] > 0 ? sol[i] : sol[i] + REST)<<"\n";
    out.close();
    return 0;
}