#include <fstream>
using namespace std;

const int NMAX = 100001;
const char in[] = "aib.in";
const char out[] = "aib.out";

int N,arb[NMAX],value,M;
char bytes[NMAX];

ifstream fin(in);
ofstream fout(out);

void compute(int N)
{
	int i;
	
	bytes[1] = 0;
	
	for(i=2; i<=N; i++)
		if(i % 2 == 0)
			bytes[i] = 1 + bytes[i>>1];
		else
			bytes[i] = 0;
}

void update(int poz)
{	
	while(poz <= N)
	{
		arb[poz] += value;
		poz += (1<<bytes[poz]);
	}
}

int query(int a)
{
	int ans = 0;
	while(a > 0)
	{
		ans += arb[a];
		a -= (1<<bytes[a]);
	}
	return ans;
}



int bsearch(int value)
{
	int left,right,center,sum;
	
	left = 1;
	right = N;
	
	while(left <= right)
	{
		center = (left + right)>>1;
		sum = query(center);
		if(sum == value)
			return center;
		if(sum < value)
			left = center + 1;
		else
			right = center - 1;
	}
	
	return -1;
}

int main()
{
	fin>>N;
	fin>>M;
	
	compute(N);
	
	int i,type,a,b;
	
	for(i=1; i<=N; i++)
	{
		fin>>value;
		update(i);
	}
	
	for(i=1; i<=M; i++)
	{
		fin>>type;
		switch(type)
		{
			case 0: fin>>a>>b; value = b; update(a); break;
			case 1: fin>>a>>b; fout<<(query(b) - query(a-1))<<'\n'; break;
			case 2: fin>>a; fout<<bsearch(a)<<'\n'; break;
		}
	}
		
	fin.close();
	fout.close();
}