#include <fstream>
#include <algorithm>
#define lsb(x) x & (-x)
#define int long long

using namespace std;

ifstream cin ("distincte.in");
ofstream cout ("distincte.out");

const int MOD = 666013;
const int N = 1e5;
int last[N + 1], a[N + 1], sum[N + 1], rez[N + 1];

struct ceva
{
    int x, y, ind;
}q[N + 1];

int n, m, k;

namespace aib
{
    int aib[N + 1];
    void update (int pos, int val)
    {
        for (int i = pos; i <= n; i += lsb(i))
            aib[i] += val;
    }
    int query (int pos)
    {
        int s = 0;
        for (int i = pos; i >= 1; i -= lsb(i))
            s += aib[i];
        return s;
    }
};

namespace v = aib;

signed main()
{
    cin >> n >> k >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], sum[i] = (sum[i - 1] + a[i]) % MOD;
    for (int i = 1; i <= m; ++i)
        cin >> q[i].x >> q[i].y, q[i].ind = i;
    sort (q + 1, q + m + 1, [](const ceva &a, const ceva &b){return a.y < b.y;});
    int dr = 1;
    for (int i = 1; i <= m; ++i)
    {
        while (dr <= q[i].y)
        {
            if (last[a[dr]])
                v::update(last[a[dr]], a[dr]);
            last[a[dr]] = dr;
            ++dr;
        }
        int val = (v::query(q[i].y) - v::query(q[i].x - 1) + MOD) % MOD;
        int qry = (sum[q[i].y] - sum[q[i].x - 1] + MOD) % MOD;
        rez[q[i].ind] = ((qry - val + MOD) % MOD);
    }
    for (int i = 1; i <= m; ++i)
        cout << rez[i] << '\n';
    return 0;
}