#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=5e5+5,M=N*45+5,K=31650,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,k,x,y,z,A[N],Ro[N];
namespace CT{
	int L[M],R[M],f[M],Ct;ll Sum[M];
	void CP(int &v){f[++Ct]=f[v];Sum[Ct]=Sum[v];L[Ct]=L[v];R[Ct]=R[v];v=Ct;}
	void add(int x,int &v,int l=1,int r=n){
		CP(v);f[v]++;Sum[v]+=x;if(l==r) return;
		int m=l+r>>1;x<=m?add(x,L[v],l,m):add(x,R[v],m+1,r);
	}
	ll kth(int x,int v1,int v2,int l=1,int r=n){
		if(l==r) return x*l;int m=l+r>>1;
		if(x<=f[R[v1]]+f[R[v2]]) return kth(x,R[v1],R[v2],m+1,r);
		return Sum[R[v2]]+Sum[R[v1]]+kth(x-f[R[v2]]-f[R[v1]],L[v1],L[v2],l,m);
	}
}
void Solve(){
	int i,j;scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&A[i]),Ro[i]=Ro[i-1],CT::add(A[i],Ro[i]);
	while(m--){
		scanf("%d%d%d",&z,&x,&y);
		CT::add(z,Ro[0]);
		printf("%lld\n",CT::kth(y,Ro[y],Ro[0])-CT::kth(x-1,Ro[x-1],Ro[0]));
	}
}
int main(){
	int t;
	// scanf("%d",&t);
	t=1;
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}