/*
* File: cuburi2.cpp
* Author: marius
*
* Created on June 23, 2010, 9:37 AM
*/
#include <stdio.h>
#include <map>
#include <vector>
using namespace std;
long long s[5005];
class ans{
ans(){
l=0;c=0;
}
public:
ans(int l,int c){
this->l=l;
this->c=c;
}
int l;int c;
};
map<int,vector<ans> > m;
#define IT map<int,vector<ans> >::iterator
inline int abs(int x) {return x<0?(-x):x ;}
inline long long vv(int x,int y){return (s[y]-s[x-1]);}
inline long long vv(int x) {return vv(x,x );}
void calc(int i, int y,vector<ans>& v){
int j=i+v.size();
if(!v.size())
v.push_back(ans(i,0));
int l=v.back().l,c=v.back().c;
while(j<y){
j++;
c+=abs(l-j)*vv(j);
while( vv(i,l)<vv(l+1,j)&&l<j){
c+=vv(i,l)-vv(l+1,j);
l++;
}
v.push_back(ans(l,c));
}
}
void answer(int x,int y){
if(x==y){
printf("%d 0",x);
return;
}
IT it=m.find(x);
if(it==m.end()){
vector<ans> v;
calc(x,y,v);
printf("%d %d\n",v.back().l,v.back().c);
return;
}
vector<ans> *v;
if(v->size()>y-x){
printf("%d %d\n",v->at(y-x).l,v->at(y-x).c);
return;
}
calc(x,y,*v);
printf("%d %d\n",v->back().l,v->back().c);
}
int main(int argc, char** argv) {
freopen("cuburi2.in","r",stdin);
freopen("cuburi2.out","w",stdout);
int n,m,x;
scanf("%d%d%lld",&n,&m,s+1);
for(int i=1;i<n;i++){
scanf("%d",&x);
s[i+1]=s[i]+x;
}
int y;
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
answer(x,y);
}
return 0;
}
/*int i=1,j=1;loc[1][1]=1;cost[1][1]=0;
while(i<n){
while(j<=n){
int l=loc[i][j],c=cost[i][j];
j++;
c+=abs(l-j)*v(j);
while( v(i,l)<v(l+1,j)&&l<j){
c+=v(i,l)-v(l+1,j);
l++;
}
loc[i][j]=l;
cost[i][j]=c;
}
/*i++;
if(i==n)
break;
while(j>=i){
int l=loc[i][j],c=cost[i][j];
c-=abs(l-j)*v(j);
j--;
while(v(i,j)>v(l,j)&&l>i){
c+=v(l,j)-v(i,l);
l--;
}
loc[i][j]=l;
cost[i][j]=c;
}//*
i++;j=i;loc[i][i]=i;cost[i][i]=0;
}*/