#include <bits/stdc++.h>

const std :: string FILENAME = "distincte";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 1e5 + 5;

const int mod = 666013;

int n;

int m;

int k;

int cnt;

int v[NMAX];

int last[NMAX];

int ans[NMAX];

int arb[NMAX];

std :: pair <std :: pair <int, int>, int> q[NMAX];

void update(int x, int val)
{
    while(x <= n)
    {
        arb[x] += val;

        arb[x] += mod;

        arb[x] %= mod;

        x += (x & (-x));
    }
}

int query(int x)
{
    int s = 0;

    while(x)
    {
        s += arb[x];

        s %= mod;

        x -= (x & (-x));
    }

    return s;
}

int main()
{

    f >> n >> k >> m;

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

    for(int i = 1; i <= m; i ++)
    {
        f >> q[i].first.second >> q[i].first.first;

        q[i].second = i;
    }

    std :: sort(q + 1, q + m + 1);

    cnt = 1;

    for(int i = 1; i <= n; i ++)
    {
        if(last[v[i]])
        {
            update(last[v[i]], - v[i]);
        }

        last[v[i]] = i;

        update(last[v[i]], v[i]);

        while(q[cnt].first.first == i)
        {
            ans[q[cnt].second] = (query(q[cnt].first.first) - query(q[cnt].first.second) + mod) % mod;

            cnt ++;
        }
    }

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

    return 0;
}