#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define mod 666013
#define ll long long
using namespace std;
ll v[100005];
ll n, k, m, bloc, fr[100005], a, b, ans[100005];
ll suma;
struct mo
{
    ll lo, hi, idx;
    bool operator <(const mo & ob) const
    {
        if(1ll * lo / bloc == 1ll * ob.lo / bloc)
        {
            return hi < ob.hi;
        }
        return lo / bloc < ob.lo / bloc;
    }
} q[100005];
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int32_t main(int argc, char * argv[])
{
    fin >> n >> k >> m;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i];
    }
    bloc = (ll)sqrt(n);
    for(int i = 1; i <= m; ++i)
    {
        fin >> a >> b;
        q[i].lo = a, q[i].hi = b, q[i].idx = i;
    }
    sort(q + 1, q + m + 1);
    ll stcur = 0, drcur = -1;
    for(int i = 1; i <= m; ++i)
    {
        int l = q[i].lo, r = q[i].hi;
        while(drcur < r)
        {
            drcur++;
            if(drcur >= 1 && drcur <= n && fr[v[drcur]] == 0)
            {
                suma = (1ll * v[drcur] + suma)% mod;
            }
            fr[v[drcur]]++;

        }
        while(stcur > l)
        {
            stcur--;
            if(stcur >= 1 && stcur <= n && fr[v[stcur]] == 0)
            {
                suma = (1ll *  v[stcur] + suma) % mod;
            }
            fr[v[stcur]]++;
        }
        while(stcur < l)
        {
            if(stcur >= 1 && stcur <= n && fr[v[stcur]] == 1)
            {
                suma = (suma - 1ll * v[stcur] + mod) % mod;
            }
            fr[v[stcur]]--;
            stcur++;
        }
        while(drcur > r)
        {
            if(drcur >= 1 && drcur <= n && fr[v[drcur]] == 1)
            {
                suma = (suma - 1ll * v[drcur] + mod) % mod;
            }
            fr[v[drcur]]--;
            drcur--;
        }
        ans[q[i].idx] = 1ll * suma % mod;
    }
    for(int i = 1; i <= m; ++i)
    {
        fout << ans[i] * 1ll << '\n';
    }
    return 0;
}