var f,g:text;
    n,m,i,x,y,j,k,t,temp,nc,nr,poz:longint;
    a:array[1..10000] of longint;
    min,s:array[1..15] of byte;
begin
  assign(f,'cuburi2.in'); reset(f);
  assign(g,'cuburi2.out'); rewrite(g);
  read(f,n,m);
  for i:=1 to n do read(f,a[i]);
  for i:=1 to 13 do min[i]:=9;
  for i:=1 to m do
    begin
      read(f,x,y);
      for j:=1 to 13 do min[j]:=9;
      for j:=x to y do
        begin
          for k:=1 to 13 do s[k]:=0;
          for k:=x to j-1 do
            begin
              temp:=a[k]*(j-k);
              nc:=0;
              t:=0;
              while temp<>0 do
                begin
                  inc(nc);
                  s[13-nc+1]:=s[13-nc+1]+temp mod 10+t;
                  if s[13-nc+1]>=10 then begin t:=1; s[13-nc+1]:=s[13-nc+1] mod 10; end
                                   else t:=0;
                  temp:=temp div 10;
                end;
              if t=1 then s[13-nc]:=s[13-nc]+1;
            end;
          for k:=j+1 to y do
            begin
              temp:=a[k]*(k-j);
              nc:=0;
              t:=0;
              while temp<>0 do
                begin
                  inc(nc);
                  s[13-nc+1]:=s[13-nc+1]+temp mod 10+t;
                  if s[13-nc+1]>=10 then begin t:=1; s[13-nc+1]:=s[13-nc+1] mod 10; end
                                   else t:=0;
                  temp:=temp div 10;
                end;
              if t=1 then s[13-nc]:=s[13-nc]+1;
            end;
          for k:=1 to 13 do
            if s[k]<min[k] then
              begin
                nr:=j;
                min:=s;
                break;
              end
                           else
                           if s[k]>min[k] then break;
        end;
      for j:=1 to 13 do if min[j]<>0 then begin poz:=j; break; end;
      write(g,nr,' ');
      for j:=poz to 13 do write(g,min[j]);
      writeln(g);
    end;
  close(f); close(g);
end.