#include <fstream>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;

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

const int NMAX = 1e5 + 1;
const int MOD = 666013;
int n, aib[NMAX], k, m, v[NMAX], ans[NMAX];

struct query
{
    int l, r, i;
};

query q[NMAX];

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

int compute(int poz)
{
    int sum = 0;
    for (int i = poz; i >= 1; i -= i & -i)
        sum += aib[i];
    return sum;
}

vector<pair<int, int>> points;

inline bool cmp(const query &q1, const query &q2)
{
    if (q1.r == q2.r)
        return q1.l > q2.l;
    return q1.r > q2.r;
}

signed main()
{
    fin >> n >> k >> m;

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

    for (int i = n; i >= 1; --i)
    {
        points.push_back({ans[v[i]], i});
        ans[v[i]] = i;
    }

    for (int i = 1; i <= m; ++i)
    {
        fin >> q[i].l >> q[i].r;
        q[i].i = i;
    }

    sort(points.begin(), points.end(), greater<pair<int, int>>());
    sort(q + 1, q + m + 1, cmp);

    int index_points = 0;
    for (int i = 1; i <= m; ++i)
    {
        while (index_points < points.size() && points[index_points].first > q[i].r)
        {
            update(points[index_points].second, v[points[index_points].second]);
            ++index_points;
        }
        ans[q[i].i] = (compute(q[i].r) - compute(q[i].l - 1)) % 666013;
    }

    for (int i = 1; i <= m; ++i)
        fout << ans[i] << '\n';

    return 0;
}