#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 100010, MOD = 666013;

int N, M, K, V[NMAX], Prev[NMAX];
pair<int, pair<int, int> > Q[NMAX];
long long FT[NMAX], Ans[NMAX];

int LSB(int X)
{
    return (X & (X - 1)) ^ X;
}

void Update(int Pos, int Val)
{
    if(Pos == 0) return ;
    for(; Pos <= N; Pos += LSB(Pos))
        FT[Pos] += Val;
}

long long Ask(int Pos)
{
    long long Ans = 0;
    for(; Pos; Pos -= LSB(Pos))
        Ans += FT[Pos];
    return Ans;
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    
    scanf("%i %i %i", &N, &K, &M);
    for(int i = 1; i <= N; ++ i) scanf("%i", &V[i]);
    
    for(int i = 1; i <= M; ++ i)
    {
        scanf("%i %i", &Q[i].second.first, &Q[i].first);
        Q[i].second.second = i;
    }
    
    sort(Q + 1, Q + M + 1);
    
    int Ptr = 1;
    for(int i = 1; i <= M; ++ i)
    {
        while(Ptr <= Q[i].first)
        {
            Update(Prev[V[Ptr]], -V[Ptr]);
            Update(Ptr, V[Ptr]);
            Prev[V[Ptr]] = Ptr;
            Ptr ++;
        }
        
        Ans[Q[i].second.second] = (Ask(Q[i].first) - Ask(Q[i].second.first - 1)) % MOD;
    }
    
    for(int i = 1; i <= M; ++ i)
        printf("%i\n", Ans[i]);
}