#include <fstream>
#include <cstdio>
#include <algorithm>
#define VAL 100005
#define MOD 666013

using namespace std;

struct interval
{
    int st, dr, ind;
};

interval Q[VAL];

int N, K, M, i, j, rad;
int v[VAL], ap[VAL];
int MoLeft, MoRight;
int ANS, answer[VAL];

bool cmp(interval A, interval B)
{
    int bucketA=A.st / rad;
    int bucketB=B.st / rad;
    if (bucketA==bucketB)
      return A.dr<B.dr;
    return bucketA<bucketB;
}

char buff[VAL];
int poz=0;

int Read_INT()
{
    int nr=0;
    while (buff[poz]<'0' || buff[poz]>'9')
      if (++poz==VAL)
        fread(buff, 1, VAL, stdin), poz=0;
    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        nr=nr*10+buff[poz]-'0';
        if (++poz==VAL)
          fread(buff, 1, VAL, stdin), poz=0;
    }
    return nr;
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    N=Read_INT();
    K=Read_INT();
    M=Read_INT();
    for (i=1; i<=N; i++)
      v[i]=Read_INT();
    for (i=1; i<=M; i++)
    {
        Q[i].st=Read_INT();
        Q[i].dr=Read_INT();
        Q[i].ind=i;
    }
    while (rad*rad<=N)
      rad++;
    rad--;
    sort(Q+1, Q+M+1, cmp);
    MoLeft=1;
    MoRight=0;
    for (i=1; i<=M; i++)
    {
        while (MoRight<Q[i].dr)
        {
            MoRight++;
            ap[v[MoRight]]++;
            if (ap[v[MoRight]]==1)
            {
                ANS+=v[MoRight];
                if (ANS>=MOD)
                  ANS-=MOD;
            }
        }
        while (MoRight>Q[i].dr)
        {
            ap[v[MoRight]]--;
            if (ap[v[MoRight]]==0)
            {
                ANS-=v[MoRight];
                if (ANS<0)
                  ANS+=MOD;
            }
            MoRight--;
        }
        while (MoLeft>Q[i].st)
        {
            MoLeft--;
            ap[v[MoLeft]]++;
            if (ap[v[MoLeft]]==1)
            {
                ANS+=v[MoLeft];
                if (ANS>=MOD)
                  ANS-=MOD;
            }
        }
        while (MoLeft<Q[i].st)
        {
            ap[v[MoLeft]]--;
            if (ap[v[MoLeft]]==0)
            {
                ANS-=v[MoLeft];
                if (ANS<0)
                  ANS+=MOD;
            }
            MoLeft++;
        }
        answer[Q[i].ind]=ANS;
    }
    for (i=1; i<=M; i++)
      printf("%d\n", answer[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}