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

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;
long long ANS, answer[VAL];

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

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    scanf("%d %d %d", &N, &K, &M);
    for (i=1; i<=N; i++)
      scanf("%d", &v[i]);
    for (i=1; i<=M; i++)
    {
        scanf("%d %d", &Q[i].st, &Q[i].dr);
        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];
        }
        while (MoRight>Q[i].dr)
        {
            ap[v[MoRight]]--;
            if (ap[v[MoRight]]==0)
              ANS-=v[MoRight];
            MoRight--;
        }
        while (MoLeft>Q[i].st)
        {
            MoLeft--;
            ap[v[MoLeft]]++;
            if (ap[v[MoLeft]]==1)
              ANS+=v[MoLeft];
        }
        while (MoLeft<Q[i].st)
        {
            ap[v[MoLeft]]--;
            if (ap[v[MoLeft]]==0)
              ANS-=v[MoLeft];
            MoLeft++;
        }
        answer[Q[i].ind]=ANS;
    }
    for (i=1; i<=M; i++)
      printf("%lld\n", answer[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}