#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
const int N = 500050;
const int S = 710;
int bl[N],br[N],a[N],b[N];
priority_queue<int,vector<int>,greater<int>> q[N];
priority_queue<int> u[N];
int sum[N];
void rebuild(int id) {
	if(u[id].empty()) return ;
	for(int x,i=bl[id];i<=br[id];i++) {
		x=u[id].top();
		if(a[i]<x) u[id].pop(),u[id].push(a[i]),a[i]=x;
	}
	while(!u[id].empty()) u[id].pop();
}
int query(int x,int y,int w) {
	int i;
	if(b[x]==b[y]) {
		int id=b[x];
		if(x==bl[id]&&y==br[id]) {
			int rev=q[id].top();
			if(rev>w) return w;
			sum[id]-=rev,sum[id]+=w;
			q[id].pop(),q[id].push(w),u[id].push(w);
			return rev;
		} else {
			rebuild(id);
			for(i=x;i<=y;i++) if(a[i]<w) swap(a[i],w);
			while(!q[id].empty()) q[id].pop();
			sum[id]=0;
			for(i=bl[id];i<=br[id];i++) q[id].push(a[i]),sum[id]+=a[i];
			return w;
		}
	} else {
		for(i=b[x];i<=b[y];i++) w=query(max(x,bl[i]),min(y,br[i]),w);
		return w;
	}
}
int get(int x,int y) {
	int i;
	if(b[x]==b[y]) {
		int id=b[x];
		if(x==bl[id]&&y==br[id]) {
			return q[id].top();
		} else {
			rebuild(id);
			while(!q[id].empty()) q[id].pop();
			sum[id]=0;
			for(i=bl[id];i<=br[id];i++) q[id].push(a[i]),sum[id]+=a[i];
			int ans=0;
			for(i=x;i<=y;i++) ans+=a[i];
			return ans;
		}
	} else {
		int ans=0;
		for(i=b[x];i<=b[y];i++) ans+=get(max(x,bl[i]),min(y,br[i]));
		return ans;
	}
}
int main() {
	// freopen("1.in","r",stdin);
	int n,i,T,u,v,w,l,j;
	fin>>n>>T;
	for(i=1;i<=n;i++) fin>>a[i];
	for(i=1;;i++) {
		bl[i]=br[i-1]+1;
		br[i]=bl[i]+S-1;
		if(br[i]>=n) {
			l=i,br[i]=n;
			break;
		}
	}
	for(i=1;i<=l;i++) {
		for(j=bl[i];j<=br[i];j++) {
			b[j]=i;
			q[i].push(a[j]);
			sum[i]+=a[j];
		}
	}
	while(T--) {
		fin>>w>>u>>v;
		query(1,n,w);
		fout<<get(u,v)<<'\n';
	}
	return 0;
}
/*
6 8
1 6 1 3 5 4
2 3 6
3 3 4
2 4 4
6 3 5
4 1 1
4 2 3
2 4 6
1 3 3
*/