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

using namespace std;

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

const int NMAX = 100000 + 5;
const int MOD = 666013;

struct query
{
    int index;
    int left;

    query()
    {
        index = 0;
        left = 0;
    }

    query(int _index, int _left)
    {
        index = _index;
        left = _left;
    }
};

int n, k, m;
int v[NMAX], aib[NMAX], poz[NMAX];
long long int sol[NMAX];
vector<query> q[NMAX];
query qr;

void read()
{
    int x, y;

    fin >> n >> k >> m;

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

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

int zeros(int x)
{
    return ( (x ^ (x - 1)) & x );
}

void add(int x, int q)
{
    for (int i = x; i <= n; i += zeros(i))
        aib[i] += q;
}

long long int compute(int x)
{
    long long int ret = 0;

    for (int i = x; i > 0; i -= zeros(i))
        ret += aib[i];

    return ret;
}

void grow()
{
    for (int i = 1; i <= n; ++i)
    {
        add(i, v[i]);

        if (poz[v[i]])
            add(poz[v[i]], -v[i]);
        poz[v[i]] = i;

        for (vector<query>::iterator it = q[i].begin(); it != q[i].end(); ++it)
        {
            qr = *it;
            sol[qr.index] = compute(i) - compute(qr.left - 1);
        }
    }
}

void write()
{
    for (int i = 1; i <= m; ++i)
        fout << sol[i] % MOD << '\n';
}

int main()
{
    read();
    grow();
    write();

    return 0;
}