var aib:array [0..100000] of longint;
    n, m, i, j, c, x, y, k, sum1, sum2:longint;
    f, g:text;
    buf1, buf2:array [1.. 1 shl 17] of char;

{Calculeaza numarul de 0-uri de la sfarsitul lui a
si returneaza valoarea 2^k unde k e numarul de 0}
function bin(a:longint):longint;
var aa:longint;
  begin
  aa:=1;
  while a mod 2 = 0 do
    begin
    aa:=aa*2;
    a:=a div 2;
    end;
  bin:=aa;
  end;

{Adaugarea elementului b pe pozitia a in arborele de intervale}
procedure ad(a, b:longint);
var zero:longint;
  begin
  aib[a]:=aib[a]+b;
  zero:=bin (a);
  if a + zero <= n then ad(a+zero, b);
  end;

{Calcueaza in s suma primelor a numere}
procedure sum (a:longint; var s:longint);
var zero:longint;
  begin
  s:=s+aib[a];
  zero:=bin(a);
  if a-zero > 0 then sum(a-zero, s);
  end;

{Cauta binar suma c-variabila globala}
procedure cautbin (a, b:longint);   {a, b capetele intervalului, c val cautata}
var m, su:longint;
  begin
  if a<=b then
    begin
    m := (a+b) div 2;
    su:=0;
    sum(m, su);
    if x<=su then
      begin
      if x = su then k := m;
      cautbin (a, m-1)
      end
                 else
      begin
      cautbin (m+1, b);
      end;
    end;
  end;


begin
assign (f, 'aib.in'); settextbuf (f, buf1); reset (f);
assign (g, 'aib.out'); settextbuf (g, buf2); rewrite (g);

read (f, n, m );
for i := 1 to n do
  begin
  read (f, x);
  ad (i, x);
  end;

for i := 1 to m do
  begin
  read (f, c);
  case c of
    0:begin
      readln (f, x, y);
      ad(x, y);
      end;
    1:begin
      readln (f, x, y);
      sum1:=0; sum2:=0;
      if x <> 1 then sum(x-1, sum1);
      sum(y, sum2);
      writeln (g, sum2-sum1);
      end;
    2:begin
      readln (f, x);
      k:=-1;
      cautbin (1, n);
      writeln (g, k);
      end;
    end;
  end;

close (f); close (g);
end.