#include <bits/stdc++.h>

#define int long long

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int MOD = 666013;
const int NMAX = 100000;

int N, K, M;
int v[NMAX + 5];
int ans[NMAX + 5];
int frecv[NMAX + 5];
struct elem
{
    int idx;
    int st, dr;
    int sqrt_idx;
    bool operator < (const elem &other) const
    {
        if(sqrt_idx != other.sqrt_idx)
        {
            return make_pair(st, dr) < make_pair(other.st, other.dr);
        }
        if(sqrt_idx & 1)
        {
            return dr < other.dr;
        }
        else
        {
            return dr > other.dr;
        }
    }
};
elem bucket[NMAX + 5];

signed main()
{
    fin >> N >> K >> M;
    for(int i = 1; i <= N; i ++)
    {
        fin >> v[i];
    }
    const int block = sqrt(N);
    for(int i = 1; i <= M; i ++)
    {
        int l, r;
        fin >> l >> r;
        bucket[i].idx = i;
        bucket[i].st = l;
        bucket[i].dr = r;
        bucket[i].sqrt_idx = l / block;
    }
    sort(bucket + 1, bucket + M + 1);
    int suma = 0;
    for(int i = bucket[1].st; i <= bucket[1].dr; i ++)
    {
        if(frecv[v[i]] == 0)
        {
            suma += v[i];
            suma %= MOD;
        }
        frecv[v[i]] ++;
    }

    ans[bucket[1].idx] = suma;
    int st = bucket[1].st, dr = bucket[1].dr;
    for(int i = 2; i <= M; i ++)
    {
        while(st > bucket[i].st)
        {
            st--;
            if(frecv[v[st]] == 0)
            {
                suma += v[st];
                suma %= MOD;
            }
            frecv[v[st]]++;
        }
        while(st < bucket[i].st)
        {
            if(frecv[v[st]] == 1)
            {
                suma -= v[st];
                if(suma < 0)
                {
                    suma += MOD;
                }
            }
            frecv[v[st]] --;
            st ++;
        }
        while(dr < bucket[i].dr)
        {
            dr++;
            if(frecv[v[dr]] == 0)
            {
                suma += v[dr];
                suma %= MOD;
            }
            frecv[v[dr]] ++;
        }
        while(dr > bucket[i].dr)
        {
            if(frecv[v[dr]] == 1)
            {
                suma -= v[dr];
                if(suma < 0)
                {
                    suma += MOD;
                }
            }
            frecv[v[dr]]--;
            dr--;
        }
        ans[bucket[i].idx] = suma;
    }
    for(int i = 1; i <= M; i ++)
    {
        fout << ans[i] << '\n';
    }
    fout << '\n';
    return 0;
}