#include <bits/stdc++.h>

const std :: string FILENAME = "distincte";

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

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

const long long NMAX = 1e5 + 5;

const long long mod = 666013;

long long n;

long long m;

long long k;

long long cnt;

long long v[NMAX];

long long last[NMAX];

long long ans[NMAX];

long long arb[NMAX];

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

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

        arb[x] += mod;

        arb[x] %= mod;

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

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

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

        s += mod;

        s %= mod;

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

    return s;
}

int main()
{

    f >> n >> k >> m;

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

    for(long long 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(long long 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(long long i = 1; i <= m; i ++)
    {
        g << ans[i] << '\n';
    }

    return 0;
}