#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MOD = 666013;

const int N_MAX = 100002;
const int M_MAX = 100002;
const int K_MAX = 100002;
const int BUFFER_SIZE = 1000002;

FILE* fin = fopen("distincte.in", "r");
ofstream fout ("distincte.out");

char buffer[BUFFER_SIZE];
int pos = -1;

void read_buffer ()
{
    fread(buffer, sizeof(char), BUFFER_SIZE, fin);
}

char read_char ()
{
    pos++;
    if(pos == BUFFER_SIZE)
    {
        read_buffer();
        pos = 0;
    }
    return buffer[pos];
}

int read_int ()
{
    char c;
    while(!isdigit(c = read_char()));
    int ans = 0;
    while(isdigit(c))
    {
        ans = ans * 10 + c - '0';
        c = read_char();
    }
    return ans;
}

int n, k, m;

int v[N_MAX];

int last[K_MAX];
int nap[N_MAX];

struct Query
{
    int l, r;
    int index;
};

bool operator < (const Query &a, const Query &b)
{
    return a.l < b.l;
}

Query queries[M_MAX];

int answer[M_MAX];

ll aib[N_MAX];

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

ll query (int pos)
{
    ll ans = 0;
    for(int i = pos; i >= 1; i -= i&(-i))
        ans += aib[i];
    return ans;
}

int main()
{
    read_buffer();
    n = read_int();
    k = read_int();
    m = read_int();
    for(int i = 1; i <= n; i++)
        v[i] = read_int();
    for(int i = n; i >= 1; i--)
    {
        nap[i] = last[v[i]];
        last[v[i]] = i;
    }
    for(int i = 1; i <= m; i++)
    {
        queries[i].l = read_int();
        queries[i].r = read_int();
        queries[i].index = i;
    }
    sort(queries + 1, queries + m + 1);
    int pos = 1;
    for(int i = 1; i <= k; i++)
        if(last[i] > 0)
            update(last[i], i);
    for(int i = 1; i <= m; i++)
    {
        while(pos < queries[i].l)
        {
            update(pos, -v[pos]);
            if(nap[pos] > 0)
                update(nap[pos], v[pos]);
            pos++;
        }
        answer[queries[i].index] = query(queries[i].r) % MOD;
    }
    for(int i = 1; i <= m; i++)
        fout << answer[i] << "\n";
    return 0;
}