#include<cstdio>
struct node{
	node *c[2];
	int l,r,le,re,ml,mr,sum,lmax,rmax,mmax;
	void print(){
		printf("%d %d %d\n",ml,mr,mmax);
	}
	node(int L,int R){
		l=L,r=R,c[0]=c[1]=NULL;
		le=re=ml=mr=sum=lmax=rmax=mmax=0;
	}
	void update(){
		sum=c[0]->sum+c[1]->sum;
		le=c[0]->le,lmax=c[0]->lmax;
		re=c[1]->re,rmax=c[1]->rmax;
		ml=c[0]->ml,mr=c[0]->mr,mmax=c[0]->mmax;
		if(c[0]->sum+c[1]->lmax> lmax) lmax=c[0]->sum+c[1]->lmax,le=c[1]->le;
		if(c[1]->sum+c[0]->rmax>=rmax) rmax=c[1]->sum+c[0]->rmax,re=c[0]->re;
		if(c[0]->rmax+c[1]->lmax>mmax) ml=c[0]->re,mr=c[1]->le,mmax=c[0]->rmax+c[1]->lmax;
		if(c[1]->mmax>mmax) ml=c[1]->ml,mr=c[1]->mr,mmax=c[1]->mmax;
	}
};
int s,t,a[100001];
void build(node *&o,int l,int r){
	o=new node(l,r);
	if(l==r){
		o->le=o->re=o->ml=o->mr=r;
		o->sum=o->lmax=o->rmax=o->mmax=a[r];
		return;
	}
	int mid=(l+r)>>1;
	build(o->c[0],l,mid),build(o->c[1],mid+1,r);
	o->update();
}
node *query(node *o){
	if(s<=o->l&&o->r<=t) return o;
	int mid=(o->l+o->r)>>1;
	if(mid>=t) return query(o->c[0]);
	else if(mid<s) return query(o->c[1]);
	else{
		node *res=new node(s,t);
		res->c[0]=query(o->c[0]),res->c[1]=query(o->c[1]);
		res->l=res->c[0]->l,res->r=res->c[1]->r,res->update();
		return res;
	}
}
int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	node *root;
	int n,m,i;
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++) scanf("%d",&a[i]);
	build(root,1,n);
	while(m--) scanf("%d%d",&s,&t),query(root)->print();
}