#include <bits/stdc++.h>
#define maxN 100002
#define mod 666013
using namespace std;

FILE *fin = freopen("distincte.in", "r", stdin);
FILE *fout = freopen("distincte.out", "w", stdout);

int n, k, m, v[maxN];

int bucket[maxN], frq[maxN];
struct Query
{
    int l, r, idx;
    bool operator < (const Query &ot) const
    {
        if (bucket[l] == bucket[ot.l])
        {
            if (bucket[l] & 1)
                return r > ot.r;
            return r < ot.r;
        }
        return l < ot.l;
    }
} Q[maxN];

int ans, sum[maxN];

bool Disj(int l1, int r1, int l2, int r2)
{
    return (r1 < l2 || r2 < l1);
}
void Mo()
{
    sort(Q + 1, Q + m + 1);
    int sgn = 1, p;
    for (p = Q[1].l; p <= Q[1].r; ++ p)
    {
        if (!frq[v[p]]) {ans += v[p];if (ans >= mod) ans -= mod;}
        ++ frq[v[p]];
    }
    -- p;
    sum[Q[1].idx] = ans;
    for (int i = 2; i <= m; ++ i)
    {
        sgn = 1 - 2 * (bucket[Q[i].l] & 1);
        if (bucket[Q[i].l] != bucket[Q[i - 1].l])
            sgn = 1 - 2 * (Q[i].r < Q[i - 1].r);
        if (Disj(Q[i - 1].l, Q[i - 1].r, Q[i].l, Q[i].r))
        {
            for (int j = Q[i - 1].l; j <= Q[i - 1].r; ++ j)
                -- frq[v[j]];
            ans = 0;
            for (int j = Q[i].l; j <= Q[i].r; ++ j)
            {
                if (!frq[v[j]])
                {
                    ans += v[j];
                    if (ans >= mod) ans -= mod;
                }
                ++ frq[v[j]];
            }
            sum[Q[i].idx] = ans;
            p = Q[i].r;
            continue;
        }
        for (int j = Q[i - 1].l; j < Q[i].l; ++ j)
        {
            -- frq[v[j]];
            if (!frq[v[j]])
            {
                ans -= v[j];
                if (ans < 0) ans += mod;
            }
        }

        for (int j = Q[i - 1].l - 1; j >= Q[i].l; -- j)
        {
            if (!frq[v[j]])
            {
                ans += v[j];
                if (ans >= mod) ans -= mod;
            }
            ++ frq[v[j]];
        }
        while (p != Q[i].r)
        {
            p += sgn;
            if (sgn == 1)
            {
                frq[v[p]] ++;
                if (frq[v[p]] == 1)
                {
                    ans += v[p];
                    if (ans >= mod) ans -= mod;
                }
            }
            else
            {
                -- frq[v[p - sgn]];
                if (!frq[v[p - sgn]])
                {
                    ans -= v[p - sgn];
                    if (ans < 0) ans += mod;
                }
            }
        }

        sum[Q[i].idx] = ans;
    }
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    int g = sqrt(m);
    //\g = 1;
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &v[i]); v[i] %= mod;
        bucket[i] = (i - 1) / g;
    }
    for (int i = 1; i <= m; ++ i)
    {
        scanf("%d%d", &Q[i].l, &Q[i].r);
        Q[i].idx = i;
    }

    Mo();
    for (int i = 1; i <= m; ++ i)
        printf("%d\n", sum[i]);
    return 0;
}