#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int N = 1e5 + 5;

struct idk  {
    int st, dr;
} q[N];

bool cmp(int x, int y)  {
    return q[x].dr < q[y].dr;
}

inline void modulo (int &x) {
    if (x > 666013)
        x -= 666013;
    if (x < 0)
        x += 666013;
}

int n, k, m, s;
int a[N], f[N], ans[N];
vector <int> v[320];

int main()  {
    cin >> n >> k >> m;
    s = sqrt(n);
    for (int i = 1; i <= n; ++i)    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; ++i)    {
        cin >> q[i].st >> q[i].dr;
        v[q[i].st / s].push_back(i);
    }
    for (int i = 0; i <= n / s; ++i)    {
        sort (v[i].begin(), v[i].end(), cmp);
        int st = 0, dr = 0, sum = 0;
        memset(f, 0, sizeof(f));
        for (auto it : v[i])    {
            while (dr < q[it].dr)   {
                ++dr;
                if (f[a[dr]] == 0)  {
                    sum += a[dr];
                    modulo(sum);
                }
                ++f[a[dr]];
            }
            while (st < q[it].st)   {
                --f[a[st]];
                if (f[a[st]] == 0)  {
                    sum -= a[st];
                    modulo(sum);
                }
                ++st;
            }
            while (st > q[it].st)   {
                --st;
                if (f[a[st]] == 0)  {
                    sum += a[st];
                    modulo(sum);
                }
                ++f[a[st]];
            }
            ans[it] = sum;
        }
    }
    for (int i = 1; i <= m; ++i)
        cout << ans[i] << '\n';
    return 0;
}