#include <cstdio>
#define INF "sequencequery.in"
#define OUF "sequencequery.out"
#define SEGT 262144
#define NMAX 100002
int seg[2][SEGT]={0},a,b,tree;
long long sum[2][NMAX],x;
void insert(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) seg[tree][nod]=a;
	else
	{
		int mij;
		long long aux;
		mij=(li+ls)/2;
		if(a<=mij)
		{
		       	insert(2*nod,li,mij);
		}
		if(b>mij)
		{
			insert(2*nod+1,mij+1,ls);
		}
		aux=sum[tree][a];
		if(sum[tree][seg[tree][nod]]<aux) seg[tree][nod]=a;
	}
}
int query(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) return seg[tree][nod];
        else
	{
		int mij,st,dr,aux;
		mij=(li+ls)/2;
		st=dr=0;
		if(a<=mij) st=query(2*nod,li,mij);
		if(b>mij)  dr=query(2*nod+1,mij+1,ls);
		aux=0;
		if(sum[tree][st]>sum[tree][aux]) aux=st;
		if(sum[tree][dr]>sum[tree][aux]) aux=dr;
		return aux;
	}
}
int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	long long v[NMAX];
	int i,j,n,m,max1,max2;
	sum[0][0]=1;sum[0][0]=(sum[0][0]<<48)*(-1);
	sum[1][0]=sum[0][0];
	fscanf(in,"%d %d",&n,&m);
	for(i=1;i<=n;i++) fscanf(in,"%lld",v+i);
	sum[0][1]=v[1];
        for(i=2;i<=n;i++) sum[0][i]=sum[0][i-1]+v[i];
        sum[1][n]=v[n];
        for(i=n-1;i>0;i--) sum[1][i]=sum[1][i+1]+v[i];
	for(i=1;i<=n;i++)
	{
	     a=b=i;tree=0;
             insert(1,1,n);
             tree=1;
             insert(1,1,n);
	}	     
	sum[0][0]=0;
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d",&a,&b);
		tree=0;
		max1=query(1,1,n);
		tree=1;
		max2=query(1,1,n);
		//if(max1==0) max1=max2;
		//if(max2==0) max2=max1;
		printf("%d %d\n",max1,max2);
		if(max2<max1) { j=max1;max1=max2;max2=j; }
		if(max1>0) fprintf(out,"%lld\n",(sum[0][max2]-sum[0][max1-1]));
		else fprintf(out,"%lld\n",sum[0][max2]);
	}
	/*a=2;b=7;tree=0;
        printf("%d\n",query(1,1,n));
	for(i=1;i<=2*n-1;i++) printf("%d ",seg[0][i]);
	printf("\n");
        for(i=1;i<=2*n-1;i++) printf("%d ",seg[1][i]);
	printf("\n");
        for(i=1;i<=n;i++) printf("%lld ",sum[0][i]);
	printf("\n");
	for(i=1;i<=n;i++) printf("%lld ",sum[1][i]);*/
	fclose(in);fclose(out);
	return 0;
}