#include <cstdio>
#include <algorithm>

#define f first
#define s second
#define MOD 666013

using namespace std;

int v[100010], aib[100010], prv[100010], sol[100010], n, k, m;
pair < pair <int, int>, int> q[100010];

inline void add (int poz, int val)
{
    for (int i = poz; i <= n; i += i & (-i))
        aib[i] =(aib[i]+val+MOD)%MOD;
}

inline long long querry (int poz)
{
    long long sum = 0LL;
    for (int i = poz; i; i -= i & (-i))
        sum =(sum+ 1LL * aib[i]+MOD)%MOD;

    return 1LL * sum;
}

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

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

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

    for (int i = 1; i <= m; ++i)
    {
        scanf ("%d %d", &q[i].f.s, &q[i].f.f);
        q[i].s = i;
    }

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

    int nr = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (prv[v[i]]) add (prv[v[i]], -v[i]);
        add (i, v[i]);
        prv[v[i]] = i;

        while (q[nr].f.f == i)
        {
            sol[q[nr].s] = (int)(1LL * (querry (q[nr].f.f) - querry (q[nr].f.s - 1)+MOD) % MOD);
            ++nr;
        }
    }

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

    return 0;
}