#include <fstream>
#define NMAX 100100
using namespace std;

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

int A[NMAX], N, M;

void AddAib(int v, int b)
{
	int p = 0;
	while (b <= N)
	{
		A[b] += v;
		while ( !(b & (1 << p)) ) p++;
		b += (1 << p);
		p++;
	}
}
int QueryAib(int a)
{
	int p = 0, s = 0;
	while (a > 0)
	{
		s += A[a];
		while (!(a & (1 << p))) p++;
		a -= (1 << p);
		p++;
	}
	return s;
}
int SearchAib(int k)
{
	int st = 1, end = N, m;
	while (st < end)
	{
		m = (st + end) / 2;
		if (QueryAib(m) == k) return m;
		if (QueryAib(m) > k)
			end = m - 1;
		else
			st = m + 1;
		if (QueryAib(m) < k && QueryAib(m+1) > k) return -1;
	}
}
int main()
{
	int i, x, a, b;
	fin >>N >>M;
	
	for (i = 1; i <= N; i++)
		fin >>x, AddAib(x,i);
	for (i = 1; i <= M; i++)
	{
		fin >>x;
		if (x == 0) fin >>a >>b, AddAib(b,a);
		if (x == 1) fin >>a >>b, fout <<QueryAib(b) - QueryAib(a - 1) <<'\n';
		if (x == 2) fin >>a, fout <<SearchAib(a) <<'\n';
	}
	fout.close();
	return 0;
}