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

using namespace std;

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

long long  prv[100005];

struct Query
{
    long long  l, r, orig;

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

long long  N, M, K;

struct AIB
{
    long long  v[100005];

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

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

        for(long long  i = poz; i >= 1; i -= i & (-i))
            s += v[i];

        return s;
    }
}aib;

long long  v[100005], ans[100005];

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

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

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

        queries[i].orig = i;
    }

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

    long long  poz = 1;

    for(long long  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 - 1);
    }

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