#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

int n, m, k;

class SegmentTree
{
    vector <int> t;
    int _n;
    inline int mergeNodes(int a, int b)
    {
        return (a + b >= MOD ? a + b - MOD : a + b);
    }

    void update(int v, int l, int r, int pos, int val)
    {
        if(l == r)
        {
            t[v] += val;
            if(t[v] >= MOD)
                t[v] -= MOD;
            return;
        }
        int m = (l + r) / 2;
        if(pos <= m)
            update(2 * v, l, m, pos, val);
        else
            update(2 * v + 1, m + 1, r, pos, val);
        t[v] = mergeNodes(t[2 * v], t[2 * v + 1]);
    }

    int query(int v, int l, int r, int tl, int tr)
    {
        if(tl > tr)
            return 0;
        if(l == tl  &&  r == tr)
            return t[v];
        int m = (l + r) / 2;
        return mergeNodes(query(2 * v, l, m, tl, min(tr, m)), query(2 * v + 1, m + 1, r, max(m + 1, tl), tr));
    }
public :

    SegmentTree (int n)
    {
        t.resize(4 * n + 1);
        _n = n;
    }

    void update(int pos, int val)
    {
        update(1, 1, _n, pos, val);
    }
    int query(int tl, int tr)
    {
        return query(1, 1, _n, tl, tr);
    }
};

struct query
{
    int left, right, index, ans;
};
vector <query> queries;
vector <int> v, lastPos;

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);

    cin >> n >> k >> m;
    v.resize(n + 1);
    lastPos.resize(k + 1);
    SegmentTree aint(n);
    queries.resize(m + 1);

    for(int i = 1; i <= n; i ++)
        cin >> v[i];
    for(int i = 1; i <= m; i ++)
    {
        cin >> queries[i].left >> queries[i].right;
        queries[i].index = i;
    }
    sort(queries.begin() + 1, queries.end(), [] (const query &a, const query &b)
         {
             if(a.right == b.right)
                return a.left < b.left;
             return a.right < b.right;
         });

    int j = 1;
    for(int i = 1; i <= n; i ++)
    {
        if(lastPos[v[i]])
            aint.update(lastPos[v[i]], -v[i]);
        aint.update(i, v[i]);
        while(j <= m  &&  queries[j].right <= i)
        {
            queries[j].ans = aint.query(queries[j].left, queries[j].right);
            j ++;
        }
        lastPos[v[i]] = i;
    }

    sort(queries.begin() + 1, queries.end(), [] (const query &a, const query &b)
         {
             return a.index < b.index;
         });

    for(int i = 1; i <= m; i ++)
        cout << queries[i].ans << "\n";
    return 0;
}