#include <iostream>
#include <cstdio>
#include <vector>
#define MODULO 666013

using namespace std;

int v[100010];

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

    int N, M, K;

    cin >> N >> K >> M;
    for(int i = 1; i <= N; ++i)
        cin >> v[i];

    for(int i = 0; i < M; ++i)
    {
        int sum = 0;
        int l, r;
        cin >> l >> r;
        vector<int> viz(N + 1, 0);
        for(int j = l; j <= r; ++j)
        {
            if(!viz[v[j]])
            {
                viz[v[j]] = 1;
                sum += v[j];
                sum %= MODULO;
            }
        }

        cout << sum << '\n';
    }

    return 0;
}