#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
using namespace std;
int n,m,li,ri,ch[200002][2],fa[200002],rev[200002],st[200002],y[200002],top=0,cnt=1,rt=1;
long long ci,a[200002],val[200002],ad[200002],ans[200002];
vector<int>l[200002],r[200002];
vector<long long>c[200002];
inline long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
 
void print(long long x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar('0'+x%10);
}
 
bool wh(int x)
{
	return ch[fa[x]][1]==x;
}
 
void pushdown(int x)
{
	if(rev[x])
       {
	   if(ch[x][0])rev[ch[x][0]]^=1,val[ch[x][0]]*=-1,ad[ch[x][0]]*=-1,swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
	   if(ch[x][1])rev[ch[x][1]]^=1,val[ch[x][1]]*=-1,ad[ch[x][1]]*=-1,swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
	   rev[x]=0;
	   }
	if(ch[x][0])val[ch[x][0]]+=ad[x],ad[ch[x][0]]+=ad[x];
	if(ch[x][1])val[ch[x][1]]+=ad[x],ad[ch[x][1]]+=ad[x];
	ad[x]=0;
}
 
void rotate(int x)
{
	int y=fa[x],z=fa[y],id=wh(x);
	ch[z][wh(y)]=x,fa[x]=z;
	ch[y][id]=ch[x][id^1],fa[ch[x][id^1]]=y;
	ch[x][id^1]=y,fa[y]=x;
}
 
void pushall(int x)
{
	int p=x;
	while(p)st[++top]=p,p=fa[p];
	while(top>0)pushdown(st[top]),top--;
}
 
void splay(int &rt,int x)
{
	pushall(x);
	while(fa[x])
	   {
	   	long long y=fa[x],z=fa[y];
	   	if(z)
	   	   {
	   	   if(wh(x)==wh(y))rotate(y);
	   	   else rotate(x);
		   }
		rotate(x);
	   }
	rt=x;
}
 
int create(int &rt,int p,long long k,int id)
{
	ch[p][id]=++cnt,val[cnt]=k,fa[cnt]=p,splay(rt,ch[p][id]);
	return cnt;
}
 
int insert(int &rt,long long p)
{
	int x=rt;
	while(x)
	  {
	  	pushdown(x);
	  	if(val[x]==p)return x;
	  	else if(p<val[x])
	  	   {
	  	   if(!ch[x][0])return create(rt,x,p,0);
		   x=ch[x][0];
	       }
	  	else 
	  	   {
	  	   if(!ch[x][1])return create(rt,x,p,1);
		   x=ch[x][1];
	       }
	  }
	return x;
}
 
int getmin(int &rt)
{
	int x=rt;
	while(ch[x][0])pushdown(x),x=ch[x][0];
	splay(rt,x);
	return x;
}
 
int split(int &rt,long long k)
{
	int x=rt,ap=0,pr=0;
	long long ans=1e18;
	while(x)
	   {
	   	pr=x,pushdown(x);
	   	if(k>=val[x])x=ch[x][1];
	   	else if(k<val[x])
	   	   {
	   	   if(val[x]<=ans)ans=val[x],ap=x;
		   x=ch[x][0];
	       }
	   }
    splay(rt,pr);
	if(ap==0)
	   {
	   int nrt=rt;
	   rt=0;
	   return nrt;
       }
	splay(rt,ap);
	int nrt=ch[rt][0];
	fa[ch[rt][0]]=0,ch[rt][0]=0;
	return nrt;
}
 
int merge(int &rt1,int &rt2)
{
	bool flag=0;
	while(rt1&&rt2)
	   {
	   	if(!flag)
	   	   {
	   	   int p=getmin(rt1),nrt=0;
	   	   splay(rt1,p),nrt=split(rt2,val[p]),fa[nrt]=p,ch[p][0]=nrt;
	       }
	    else
	   	   {
	   	   int p=getmin(rt2),nrt=0;
	   	   splay(rt2,p),nrt=split(rt1,val[p]),fa[nrt]=p,ch[p][0]=nrt;
	       }
	    flag^=1;
	   }
	return rt1+rt2;
}
 
int main()
{
	val[1]=1e17;
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++)ci=read(),li=read(),ri=read(),l[li].push_back(i),r[ri].push_back(i),c[li].push_back(ci);
	for(int i=1;i<=n;i++)
	    {
	    	for(int j=0;j<(int)l[i].size();j++)y[l[i][j]]=insert(rt,c[i][j]);
	    	int nrt=split(rt,(a[i]-1)>>1);
	    	rev[nrt]^=1,val[nrt]*=-1,ad[nrt]*=-1,swap(ch[nrt][0],ch[nrt][1]),val[nrt]+=a[i],ad[nrt]+=a[i];
			rt=merge(rt,nrt);
	    	for(int j=0;j<(int)r[i].size();j++)splay(rt,y[r[i][j]]),ans[r[i][j]]=val[y[r[i][j]]];
		}
	for(int i=1;i<=m;i++)print(ans[i]),putchar('\n');
	return 0;
}