#include <bits/stdc++.h>

using namespace std;

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

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

int N, K, M;
int v[NMAX + 5];
int aib[NMAX + 5];
int last[NMAX + 5];
int ans[NMAX + 5];
struct elem{
    int l, r, idx;
    bool operator < (const elem &other) const
    {
        return l > other.l;
    }
};
elem ask[NMAX + 5];

void update(int poz, int val)
{
    while(poz <= N)
    {
        aib[poz] += val;
        while(aib[poz] < 0)
        {
            aib[poz] += MOD;
        }
        while(aib[poz] >= MOD)
        {
            aib[poz] -= MOD;
        }
        poz += (poz & (-poz));
    }
}

int query(int poz)
{
    int ans = 0;
    while(poz)
    {
        ans += aib[poz];
        while(ans >= MOD)
        {
            ans -= MOD;
        }
        poz -= (poz & (-poz));
    }
    return ans;
}

int main()
{
    fin >> N >> K >> M;
    for(int i = 1; i <= N; i ++)
    {
        fin >> v[i];
    }
    for(int i = 1; i <= M; i ++)
    {
        fin >> ask[i].l >> ask[i].r;
        ask[i].idx = i;
    }
    sort(ask + 1, ask + M + 1);
    int left = N + 1;
    for(int i = 1; i <= M; i ++)
    {
        while(left > ask[i].l)
        {
            left--;
            update(left, v[left]);
            if(last[v[left]] != 0)
            {
                update(last[v[left]], -v[left]);
            }
            last[v[left]] = left;
        }
        ans[ask[i].idx] = query(ask[i].r);
    }
    for(int i = 1; i <= M; i ++)
    {
        fout << ans[i] << '\n';
    }
    return 0;
}