#include <cstdio>
#include <algorithm>

#define ub(x) (x&(-x))

#define left first.second
#define right first.first
#define ord second

using namespace std;

const int Nmax = 100010;
const int MOD = 666013;

int n , k , m , i , j;
int a[Nmax] , marked[Nmax] , aib[Nmax];

pair < int , int > sol[Nmax];

pair < pair < int , int > , int > q[Nmax];

void update(int poz , int val)
{
    for (int i = poz; i <= n; i += ub(i))
        aib[i] = (aib[i] + val + MOD) % MOD;
}

int query(int poz)
{
    int ans = 0;

    for (int i = poz; i ; i -= ub(i))
        ans = (ans + aib[i]) % MOD;

    return ans;
}

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    scanf("%d %d %d", &n, &k, &m);

    for (i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d", &q[i].left, &q[i].right);
        q[i].ord = i;
    }

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

    for (j = 1 , i = 1; i <= m; ++i)
    {
        for ( ; j <= q[i].right; ++j)
        {
            if (marked[a[j]]) update(marked[a[j]] , -a[j]);

            update(j , a[j]);

            marked[a[j]] = j;
        }

        sol[i].first = q[i].ord;
        sol[i].second = (query(q[i].right) - query(q[i].left - 1) + MOD) % MOD;
    }

    sort(sol + 1 , sol + m + 1);

    for (i = 1; i <= m; ++i)
        printf("%d\n", sol[i].second);

    return 0;
}