/*
          ~Keep It Simple!~
*/




#include <stdio.h>

int aib[100001],n,m;

void Add(int value,int position)
{
 	while( position <= n )
	{
		aib[position] += value;
		position += ( position & -position);
	}
}

int Sum(int position)
{
	int S = 0;
	while( position )
	{
		S += aib[position];
		position -= ( position & -position );
	}
	return S;
}

int MinSum(int value)
{
	int position = 0,bitMask;
	for(bitMask = 1; bitMask < n; bitMask <<= 1);

	while( bitMask )
	{
		int mid = position + bitMask;
		if( mid <= n && aib[mid] <= value)
		{
			position = mid;
			value -= aib[mid]; 
			if(!value) return mid;
		}
		bitMask >>= 1;
	}
	    return -1;
}

int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);

	scanf("%d%d",&n,&m);
	
	int x,y,z;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		Add(x,i);
	}

	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);

		if( x == 0 )
		{
			scanf("%d%d",&z,&y);
			Add(y,z);
		}
		else if ( x == 1 )
		{
			scanf("%d%d",&z,&y);
			printf("%d\n",Sum(y)-Sum(z-1));
		}
		else if ( x == 2)
		{
			scanf("%d",&y);
			printf("%d\n",MinSum(y));
		}
	}
		
}