#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif

using namespace std;

#ifndef LOCAL
ifstream in("distincte.in");
ofstream out("distincte.out");
#endif

const int nmax = 1e5 + 5;
const int sqmax = 320;
const int MOD = 666013;

struct query
{
    int st, dr, ind;
    bool operator<(const query &other) const
    {
        if (dr == other.dr)
        {
            return st < other.st;
        }
        return dr < other.dr;
    }
};

int64_t sum;
int sq;
int n, m, k;
vector<query> buckets[sqmax];
int v[nmax];
int64_t ans[nmax];
int freq[nmax];

void gotodr(int &dr, int target)
{
    while (dr < target)
    {
        dr++;
        if (freq[v[dr]] == 0)
        {
            sum += v[dr];
        }
        freq[v[dr]]++;
    }
}

void gotost(int &st, int target)
{
    if (st < target)
    {
        while (st < target)
        {
            freq[v[st]]--;
            if (freq[v[st]] == 0)
            {
                sum -= v[st];
            }
            st++;
        }
    }
    else if (st > target)
    {
        while (st > target)
        {
            st--;
            if (freq[v[st]] == 0)
            {
                sum += v[st];
            }
            freq[v[st]]++;
        }
    }
}

void process(int ind)
{
    sort(buckets[ind].begin(), buckets[ind].end());
    int st, dr;
    st = dr = sq * ind + 1;
    sum = v[st];
    freq[v[st]]++;
    for (auto b : buckets[ind])
    {
        gotodr(dr, b.dr);
        gotost(st, b.st);
        ans[b.ind] = sum;
    }
    for (int i = st; i <= dr; i++)
    {
        freq[v[i]]--;
    }
    sum = 0;
}

int main()
{
    in >> n >> k >> m;
    sq = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        in >> a >> b;
        buckets[(a - 1) / sq].push_back({a, b, i});
    }
    for (int i = 0; i <= n / sq; i++)
    {
        if (buckets[i].size() != 0)
        {
            process(i);
        }
    }
    for (int i = 0; i < m; i++)
    {
        out << ans[i] % MOD << '\n';
    }
}