#include <fstream>

#define zeros(x) ( (x ^ (x - 1)) & x )

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int AIB[100005];
int N,M;

void Add(int pos, int quantity);
int Compute(int pos);
int Search(int a);
void read();
void solve();

int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	int x;
	fin>>N>>M;
	for(int i=1;i<=N;i++)
	{
		fin>>x;
		Add(i,x);
	}
}

void solve()
{
	int c,a,b;
	for(int i=0;i<M;i++)
	{
		fin>>c;
		if(c == 0)
		{
			fin>>a>>b;
			Add(a,b);
		}
		else if(c == 1)
		{
			fin>>a>>b;
			int sum = Compute(b) - Compute(a-1);
			fout<<sum<<'\n';
		}
		else
		{
			fin>>a;
			int k = Search(a);
			fout<<k<<'\n';
		}
	}
}

void Add(int pos, int quantity)
{ 
	for (int i = pos; i <= N; i += zeros(i))
	{
		AIB[i] += quantity;
	}        
}

int Compute(int pos)
{
	int sum = 0; 
	for (int i = pos; i > 0; i -= zeros(i))
	{
		sum += AIB[i];
	}        
	return sum;
}

int Search(int a)
{
	int left = 0, right = N + 1, mid = N, pos = N+1, sum = 0;
	while(left < right)
	{
		mid = (left + right) / 2;
		sum = Compute(mid);
		if(sum == a)
		{
			if(mid < pos)
			{
				pos = mid;
			}
			right = mid;
		}
		else
		{
			if(sum < a)
			{
				left = mid + 1;
			}
			else
			{
				right = mid;
			}
		}
	}
	mid = (left + right) / 2;
	sum = Compute(mid);
	if(sum == a && pos > mid)
	{
		pos = mid;
	}
	mid = (left + right) / 2;
	sum = Compute(mid+1);
	if(sum == a && pos > mid+1)
	{
		pos = mid+1;
	}
	mid = (left + right) / 2;
	sum = Compute(mid-1);
	if(sum == a && pos > mid-1)
	{
		pos = mid-1;
	}
	return (pos == N+1) ? -1 : pos;
}