#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 100005;
const int MOD = 666013;
int n, k, m, v[NMAX], last[NMAX];
long long ans[NMAX], aib[NMAX];

int lsb(int x)
{
    return (x & (-x));
}

void Update(int pos, int val)
{
    for (int i = pos;i <= n;i += lsb(i))
        aib[i] += val;
}

long long Query(int pos)
{
    long long cnt = 0;
    for (int i = pos;i >= 1;i -= lsb(i))
        cnt += aib[i];
    return cnt;
}

pair <pair <int, int>, int> seg[NMAX];

int main()
{
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    fin >> n >> k >> m;
    for (int i = 1;i <= n;++i)
    {
        fin >> v[i];
        Update(i, v[i]);
    }
    for (int i = 1;i <= m;++i)
    {
        fin >> seg[i].first.second >> seg[i].first.first;
        seg[i].second = i;
    }
    sort(seg + 1, seg + m + 1);
    int ind = 1;
    for (int i = 1;i <= m;++i)
    {
        while (ind <= seg[i].first.first)
        {
            if (last[v[ind]] != 0)
                Update(last[v[ind]], -v[ind]);
            last[v[ind]] = ind;
            ++ind;
        }
        ans[seg[i].second] = Query(seg[i].first.first) - Query(seg[i].first.second - 1);
    }
    for (int i = 1;i <= m;++i)
        fout << ans[i] % MOD << "\n";
    fin.close();
    fout.close();
    return 0;
}