#include <fstream>
#include <algorithm>

using namespace std;

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

struct qu
{
    int i, j;
    int ind;
};
qu q[100005];
int aib[100005];
int v[100005];
int last[100005];
int ans[100005];
int n, k, m;
int MOD = 666013;

void update(int p, int x)
{
    for(int i = p; i<=100003; i+=(i&-i))
    {
        aib[i] += x;
    }
}

int query(int p)
{
    int ans = 0;
    for(int i = p; i>=1; i-=(i&-i))
    {
        ans = (ans + aib[i]) % MOD;
    }
    return ans;
}

int cmp(const qu &a, const qu &b)
{
    return a.j < b.j;
}

int main()
{
    in>>n>>k>>m;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i];
    }

    for(int i = 1; i<=m; i++)
    {
        in>>q[i].i>>q[i].j;
        q[i].ind = i;
    }

    sort(q+1, q+m+1, cmp);

    int j = 1;
    for(int i = 1; i<=m; i++)
    {
        while(j <= q[i].j)
        {
            update(j, v[j]);
            if(last[v[j]] != 0)
            {
                update(last[v[j]], -v[j]);
            }
            last[v[j]] = j;
            j++;
        }
        ans[q[i].ind] = (query(q[i].j) - query(q[i].i-1)) % MOD;
        while(ans[q[i].ind] < 0)
        {
            ans[q[i].ind] += MOD;
        }
    }

    for(int i = 1; i<=m; i++)
    {
        out<<ans[i]<<'\n';
    }


    return 0;
}