#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];

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

int bucketSize;

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

Query queries[M_MAX];

int freq[K_MAX];

int answer[M_MAX];

int main()
{
    read_buffer();
    n = read_int();
    k = read_int();
    m = read_int();
    bucketSize = n / sqrt(m);
    for(int i = 1; i <= n; i++)
        v[i] = read_int();
    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 l = 1, r = 0;
    ll sum = 0;
    for(int i = 1; i <= m; i++)
    {
        while(queries[i].l < l)
        {
            l--;
            freq[v[l]]++;
            if(freq[v[l]] == 1)
                sum += v[l];
        }
        while(queries[i].r > r)
        {
            r++;
            freq[v[r]]++;
            if(freq[v[r]] == 1)
                sum += v[r];
        }
        while(queries[i].l > l)
        {
            freq[v[l]]--;
            if(freq[v[l]] == 0)
                sum -= v[l];
            l++;
        }
        while(queries[i].r < r)
        {
            freq[v[r]]--;
            if(freq[v[r]] == 0)
                sum -= v[r];
            r--;
        }
        sum = (sum % MOD + MOD) % MOD;
        answer[queries[i].index] = sum;
    }
    for(int i = 1; i <= m; i++)
        fout << answer[i] << "\n";
    return 0;
}