#include <bits/stdc++.h>

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

const int nmax = 100005;
const int mod = 666013;

class Arbore
{
public:
    int n;
    long long tree[nmax * 4];
    void update(const int id, const int val)
    {
        private_update(1, 1, n, id, val);
    }

    long long ans(const int a, const int b)
    {
        return private_ans(1, 1, n, a, b);
    }

private:
    
    void private_update(int nod, int i, int j, const int id, const int val)
    {
        if (i == j)
        {
            tree[nod] = val;
            return;
        }
        int mij = (i + j) / 2;
        if (id <= mij)
            private_update(nod * 2, i, mij, id, val);
        else
            private_update(nod * 2 + 1, mij + 1, j, id, val);
        tree[nod] = tree[nod * 2] + tree[nod * 2 + 1];
    }

    long long private_ans(int nod, int i, int j, int a, int b)
    {
        if (a <= i && j <= b)
            return tree[nod];
        int mij = (i + j) / 2;
        long long ans = 0;
        if (a <= mij)
            ans += private_ans(nod * 2, i, mij, a, b);
        if (b > mij)
            ans += private_ans(nod * 2 + 1, mij + 1, j, a, b);
        return ans;
    }
};

int last[nmax];
int prevs[nmax];
int a[nmax];
long long ans[nmax];
vector <pair <int, int> > query[nmax];

int main()
{
    int n, m, k;
    f >> n >> k >> m;
    Arbore tree{};
    tree.n = n;
    for (int i = 1; i <= n; ++ i)
    {
        int x;
        f >> x;
        if (last[x])
            prevs[i] = last[x];
        last[x] = i;
        a[i] = x;
    }
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        f >> x >> y;
        query[y].emplace_back(x, i);
    }
    for (int i = 1; i <= n; ++ i)
    {
        tree.update(i, a[i]);
        if (prevs[i])
            tree.update(prevs[i], 0);
        for (auto el : query[i])
            ans[el.second] = tree.ans(el.first, i) % mod;
    }
    for (int i = 1; i <= m; ++ i)
        g << ans[i] << '\n';
}