#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100005;
const int MOD = 666013;

ifstream cin ("distincte.in");
ofstream cout ("distincte.out");

struct data
{
    int left;
    int right;
    int index;
};

int v[NMAX], last[NMAX], previous[NMAX], dist[NMAX];

bool cmp(data a, data b)
{
    if(a.right == b.right)
        return a.left < b.left;
    else
        return a.right < b.right;
}

long long tree[4 * NMAX];

void update(int node, int st, int dr, int poz, int val)
{
    if(st == dr) {
        tree[node] = val;
        return;
    }
    int med = (st + dr) / 2;
    if(poz <= med)
        update(node * 2, st, med, poz, val);
    else
        update(node * 2 + 1, med + 1, dr, poz, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long query(int node, int st, int dr, int a, int b)
{
    long long sum = 0;
    if(a <= st && dr <= b) {
        return tree[node];
    }
    int med = (st + dr) / 2;
    if(a <= med)
        sum += query(node * 2, st, med, a, b);
    if(b > med)
        sum += query(node * 2 + 1, med + 1, dr, a, b);
    return sum;
}

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> v[i];
        dist[i] = v[i];
        if(last[v[i]] != 0)
            previous[i] = last[v[i]];
        last[v[i]] = i;
    }
    vector <data> q;
    for(int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        data elem;
        elem.left = x;
        elem.right = y;
        elem.index = i - 1;
        q.emplace_back(elem);
    }
    sort(q.begin(), q.end(), cmp);
    for(int i = q[0].right; i >= 1;  --i) {
        if(previous[i] != 0) {
            int curr = i, newcurr = 0;
            while(previous[curr] > 0) {
                newcurr = previous[curr];
                previous[curr] = 0;
                dist[newcurr] = 0;
                curr = newcurr;
            }
            dist[newcurr] = 0;
        }
        update(1, 1, n, i, dist[i]);
    }
    int lastdr = q[0].right;
    vector <long long> solution;
    solution.resize(m);
    for(auto a: q) {
        for(int i = lastdr + 1; i <= a.right; ++i) {
            if(previous[i] != 0) {
                update(1, 1, n, previous[i], 0);
            }
            update(1,1, n, i, dist[i]);
        }
        lastdr = a.right;
        solution[a.index] = query(1, 1, n, a.left, a.right) % MOD;
    }
    for(int a: solution)
        cout << a << "\n";
    return 0;
}