#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

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

int prv[100005];

struct Query
{
    int l, r, orig;

    bool operator < (const Query &other) const
    {
        if(r == other.r)
            return l < other.l;
        return r < other.r;
    }
}queries[100005];

int N, M, K;

struct AIB
{
    int v[100005];

    void update(int poz, int val)
    {
        for(int i = poz; i <= N; i += i & (-i))
            v[i] += val;
    }

    int query(int poz)
    {
        int s = 0;

        for(int i = poz; i >= 1; i -= i & (-i))
            s += v[i], s %= MOD;

        if(s < 0)
            s += MOD;

        return s;
    }
}aib;

int v[100005], ans[100005];


int main()
{
    fin >> N >> K >> M;

    for(int i = 1; i <= N; i++)
        {
            fin >> v[i];
            aib.update(i, v[i]);
        }

    for(int i = 1; i <= M; i++)
    {
        fin >> queries[i].l >> queries[i].r;

        queries[i].orig = i;
    }

    sort(queries + 1, queries + M + 1);

    int poz = 1;

    for(int i = 1; i <= M; i++)
    {
        while(poz <= queries[i].r)
        {
            if(prv[v[poz]] != 0)
                aib.update(prv[v[poz]], -v[poz]);
            prv[v[poz]] = poz;
            poz++;
        }

        ans[queries[i].orig] = aib.query(queries[i].r) - aib.query(queries[i].l);
        ans[queries[i].orig] %= MOD;

        if(ans[queries[i].orig] < 0)
            ans[queries[i].orig] += MOD;
    }

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