#include <fstream>
#include <algorithm>
#define mod 666013
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
const int Nmax = 1e5+ 5;
struct evenimente
{
    int x, y, poz;
};
evenimente ev[Nmax];
int v[Nmax], f[Nmax], ans[Nmax], aib[Nmax];
int n;
void update(int x, int val)
{
    int i;
    for(i = x; i <= n; i +=(i & -i)){
        aib[i] = (aib[i] + mod + val) % mod;
    }
}
int solve(int x)
{
    int i, sum = 0;
    for(i = x; i >= 1; i -= (i & -i))
        sum = (sum + aib[i]) % mod;
    return sum;
}
bool cmp(evenimente a, evenimente b)
{
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
int main()
{
    int m, k, i, j;
    cin >> n >> k >> m;
    for(i = 1; i <= n; i++)
        cin >> v[i];
    for(i = 1; i <= m; i++){
        cin >> ev[i].x >> ev[i].y;
        ev[i].poz = i;
    }
    sort(ev + 1, ev + m + 1, cmp);
    int last_poz = 1;
    for(i = 1; i <= m; i++){
        for(j = last_poz; j <= ev[i].y; j++){
            if(f[v[j]])
                update(f[v[j]], -v[j]);
            f[v[j]] = j;
            update(f[v[j]], v[j]);
        }
        ans[ev[i].poz] = (solve(ev[i].y) - solve(ev[i].x - 1));
        if(ans[ev[i].poz] < 0)
            ans[ev[i].poz] += mod;
        last_poz = ev[i].y;
    }
    for(i = 1; i <= m; i++)
        cout << ans[i] % mod << "\n";
    return 0;
}