#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m,sq,sum=0,cnt[N],ans[N],a[N];
struct node{
	int l,r,num;
}q[N];
bool cmp(node n1,node n2){
	if(n1.l/sq==n2.r/sq) return n1.r<=n2.r;
	return n1.l/sq<n2.l/sq;
}
void add(int x){
	int t1=pow(cnt[a[x]],2);
	cnt[a[x]]++;
	int t2=pow(cnt[a[x]],2);
	sum=sum+t2-t1;
}
void sub(int x){
	int t1=pow(cnt[a[x]],2);
	cnt[a[x]]--;
	int t2=pow(cnt[a[x]],2);
	sum=sum+t2-t1;
}
int main(){
	cin>>n>>m>>sq;
	sq=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].num=i;
	}
	int L=1,R=0;
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++){
		int l=q[i].l,r=q[i].r;
		while(L>l) add(--L);
		while(R<r) add(++R);
		while(L<l) sub(L++);
		while(R>r) sub(R--);
		ans[q[i].num]=sum;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}