1 var i,n,x,y,k,t,temp,m:longint; 2     s,fa,a:array[0..200100] of int64; 3 function find(x:longint):longint; 4  begin 5  if fa[x]<>x then fa[x]:=find(fa[x]); 6  exit(fa[x]); 7  end; 8 function lowbit(x:longint):longint; 9  begin10  exit(x and (-x));11  end;12 procedure add(x,y:int64);13  begin14  while x<=n do15   begin16   inc(s[x],y);17   inc(x,lowbit(x));18   end;19  end;20 function sum(x:int64):int64;21  begin22  sum:=0;23  while x>0 do24   begin25   inc(sum,s[x]);26   dec(x,lowbit(x));27   end;28  exit(sum);29  end;30 procedure update(x,y:longint);31  var i:longint;32  begin33  i:=find(x);34  while i<=y do35   begin36   temp:=trunc(sqrt(a[i]));37   add(i,temp-a[i]);38   a[i]:=temp;39   if a[i]=1 then fa[i]:=i+1;40   i:=find(i+1);41   end;42  end;43 procedure init;44  begin45  readln(n);46  for i:=1 to n do begin read(a[i]);fa[i]:=i;add(i,a[i]);end;47  fa[n+1]:=n+1;48  end;49 procedure main;50  begin51  readln(m);52  for i:=1 to m do53   begin54   readln(k,x,y);55   if x>y then begin t:=x;x:=y;y:=t;end;56   case k of57   2:update(x,y);58   1:writeln(sum(y)-sum(x-1));59   end;60   end;61  end;62 begin63  init;64  main;65 end.