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

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()
{
    ifstream fin ("distincte.in");
    ofstream fout ("distincte.out");
    fin >> n >> k >> m;
    bucketSize = n / sqrt(m);
    for(int i = 1; i <= n; i++)
        fin >> v[i];
    for(int i = 1; i <= m; i++)
    {
        fin >> queries[i].l >> queries[i].r;
        queries[i].index = i;
    }
    sort(queries + 1, queries + m + 1);
    int l = 1, r = 0;
    int 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];
            if(sum >= MOD)
                sum -= MOD;
        }
        while(queries[i].r > r)
        {
            r++;
            freq[v[r]]++;
            if(freq[v[r]] == 1)
                sum += v[r];
            if(sum >= MOD)
                sum -= MOD;
        }
        while(queries[i].l > l)
        {
            freq[v[l]]--;
            if(freq[v[l]] == 0)
                sum -= v[l];
            if(sum < 0)
                sum += MOD;
            l++;
        }
        while(queries[i].r < r)
        {
            freq[v[r]]--;
            if(freq[v[r]] == 0)
                sum -= v[r];
            if(sum < 0)
                sum += MOD;
            r--;
        }
        answer[queries[i].index] = sum;
    }
    for(int i = 1; i <= m; i++)
        fout << answer[i] << "\n";
    return 0;
}