#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cassert>
using namespace std;

#define PRO "aib"
void OpenFiles(int EVAL)
{
	if(EVAL)
	{
		char input[100] = PRO, output[100] = PRO;
		freopen(strcat(input, ".in"),"r",stdin);
		freopen(strcat(output,".out"),"w",stdout);
	} else
	{
		freopen("test.in","r",stdin);
		freopen("test.out","w",stdout);
	}
}

#define MAX 100001
#define INF 0xffffff

int n,a[MAX];

void Update(int idx,int val)
{
	while(idx<=n)
	{
		a[idx]+=val;
		idx+=idx&-idx;
	}
}

int Suma(int idx)
{
	int s=0;
	while(idx>0)
	{
		s+=a[idx];
		idx-=idx&-idx;
	}
	return s;
}

int BSearch(int val)
{
	int m,l=1,r=n;
	while(l<r)
	{
		m=(l+r)/2;
		if(Suma(m)<val)l=m+1; else r=m;
	}
	return Suma(l)==val?l:-1;
}

int main(int argv,char *args[])
{
	OpenFiles(argv==0);	
	// start
	int m,op,x,y;
	scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&y);
			x=i;
			Update(x,y);
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&op);
			switch(op)
			{
			case 0: scanf("%d %d",&x,&y); 
					Update(x,y); break;
			case 1: scanf("%d %d",&x,&y);
					printf("%d\n",Suma(y)-Suma(x-1)); break;
			case 2: scanf("%d",&x);
					printf("%d\n",BSearch(x)); break;
			}
		}
	return 0;
}