#include <bits/stdc++.h>

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
set<unsigned short int> S[400001];
unsigned short int x[400001];

struct Data
{unsigned short int v;
 set<unsigned short int> s;
};

void C(int nod)
{set<int> a=S[nod*2], b=S[nod*2+1];
 int c=x[nod*2], d=x[nod*2+1];

 if(a.size()<b.size())
 swap(a, b), swap(c, d);

 x[nod]=c;
 swap(S[nod], a);
 set<int>:: iterator I;
 for(I=b.begin();I!=b.end();I++)
 {int p=binary_search(S[nod].begin(), S[nod].end(), *I);

  if(p==0)S[nod].insert(*I), x[nod]+=*I;
 }
}

void Build(int nod, int st, int dr)
{if(st==dr)
 {int a;
  fin>>a;
  x[nod]=a;
  S[nod].insert(a);
 }
 else
 {int mij=(st+dr)/2;

  Build(nod*2, st, mij);
  Build(nod*2+1, mij+1, dr);

  C(nod);
 }
}

Data Query(int nod, int st, int dr, int qs, int qd)
{if(st>=qs && dr<=qd)
 {Data a;
  a.v=x[nod];
  a.s=S[nod];

  return a;
 }
 else
 {int mij=(st+dr)/2;

  if(mij>=qd)return Query(nod*2, st, mij, qs, qd);
  if(mij<qs)return Query(nod*2+1, mij+1, dr, qs, qd);

  Data a, b, c;
  b=Query(nod*2, st, mij, qs, qd), c=Query(nod*2+1, mij+1, dr, qs, qd);

  if(b.s.size()<c.s.size())swap(b, c);

  swap(a, b);
  set<int>:: iterator I;
  for(I=c.s.begin();I!=c.s.end();I++)
  {int p=binary_search(a.s.begin(), a.s.end(), *I);

   if(p==0)a.s.insert(*I), a.v+=*I;
  }
  return a;
 }
}

int main()
{   int n, k, m, a, b;
    fin>>n>>k>>m;
    Build(1, 1, n);

    for(int i=1;i<=m;i++)
    {fin>>a>>b;

     fout<<Query(1, 1, n, a, b).v<<"\n";
    }
    return 0;
}