#include<stdio.h>
#define z(a) (((a-1)^a)&a)
int sol,N,M,i,j,k,t,y,x,A[100002],m,nr,st,dr;
void ADD(int a,int b)
{
	for (int i=a;i<=N;i+=z(i))
		A[i]+=b;
}
int QUERY(int a)
{   
	sol=0;
	for (int i=a;i>=1;i-=z(i))
		sol+=A[i];
	return sol;
}
int SEARCH(int x)
{
	st=1;dr=N;
	while (st<=dr)
	{
		m=(st+dr)/2;
		nr=QUERY(m);
		if (nr==x) return m;
		if (nr<x) st=m+1;
			else dr=m-1;
	}
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++){
		scanf("%d",&x);
		ADD(i,x);}
	for (i=1;i<=M;i++){
		scanf("%d%d",&t,&x);
		if (t!=2) scanf("%d",&y);
		if (t==0) ADD(x,y);
			else if (t==1) printf("%d\n",QUERY(y)-QUERY(x-1));
				else printf("%d\n",SEARCH(x));}
}