var a:array[1..100000]of longint;
    n,m:longint;

procedure modif(x,k:longint);
begin
 while x<=n do
  begin
   inc(a[x],k);
   inc(x,(x xor (x-1))and x);
  end;
end;

function suma(x:longint):longint;
var k:longint;
begin
 k:=0;
 while x>0 do
  begin
   inc(k,a[x]);
   dec(x,(x xor (x-1))and x);
  end;
 suma:=k;
end;

function poz(x:longint):longint;
var i:longint;
begin
 poz:=-1;
 for i:=1 to n do
  if a[i]=x then begin poz:=i; break; end;
end;

procedure calc;
var i,x,y,p:longint; f,t:text;
begin
 assign(f,'aib.in');
 reset(f);
 assign(t,'aib.out');
 rewrite(t);
 readln(f,n,m);
 for i:=1 to n do
  begin
   read(f,p);
   modif(i,p);
  end;
  readln(f);
 for i:=1 to m do
  begin
   read(f,p);
   if p=0 then begin readln(f,x,y); modif(x,y); end else
    if p=1 then begin readln(f,x,y); writeln(t,suma(y)-suma(x-1)); end else
     begin readln(f,x); writeln(t,poz(x)); end;
  end;
 close(t);
 close(f);
end;

begin
 calc;
end.