#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int aint[400005];
int p[100005];
int a[100005];
int n, m, k;
vector<pair<int, int>>q[100005];
int sol[100005];

void Update(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        aint[nod] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if (poz <= mij) Update(2 * nod, st, mij, poz, val);
    else Update(2 * nod + 1, mij + 1, dr, poz, val);
    aint[nod] = (aint[2 * nod] + aint[2 * nod + 1])%666013;
}


int Query(int nod, int st, int dr, int x, int y)
{
 
    if (x <= st && dr <= y) return aint[nod];
    if (dr<x || st>y) return 0;
    int mij = (st + dr) / 2;  
    return (Query(2 * nod, st, mij, x, y) + Query(2 * nod + 1, mij + 1, dr, x, y))% 666013;
}

int main()
{
    fin >> n >> k >> m;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
        Update(1, 1, n, i, a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        q[x].push_back({ y,i });
    }
    for (int i = n; i >= 1; i--)
    {
        if (p[a[i]] != 0) Update(1, 1, n, p[a[i]], 0);
        p[a[i]] = i;
        for (auto w : q[i])
            sol[w.second] = Query(1, 1, n, i, w.first);

    }
    for (int i = 1; i <= m; i++)
        fout << sol[i] << "\n";
}