#include<fstream>
#define Nmax 100010
#define lsb(x) (x & -x)
using namespace std;

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

int i, N, M, AIB[Nmax];

void update(int x, int val)
{
	int i;
	for (i = x; i <= N; i += lsb(i))
		AIB[i] += val;
}

int query(int x)
{
	int i, res=0;
	for (i = x; i; i -= lsb(i))
		res+=AIB[i];
	return res;
}

int BinarySearch(int x)
{
	int mid, l=1, r=N;
	while (l <= r)
	{
		mid = (l + r) / 2;
		int sum = query(mid);
		if (sum < x)
			l = mid + 1;
		else
		if (sum>x)
			r = mid - 1;
		else
			return mid;
	}
	return -1;
}

int main()
{
	int op, x, a, b;
	fin >> N>>M;
	for (i = 1; i <= N; ++i)
	{
		fin >> x;
		update(i, x);
	}
	for (i = 1; i <= M; ++i)
	{
		fin >> op;
		switch (op){
		case 0:{
				   fin >> a>> b;
				   update(a, b); }break;
		case 1:{
				   fin >> a >> b;
				   fout << query(b) - query(a - 1) << '\n'; }break;
		case 2:{
				   fin >> a;
				   fout << BinarySearch(a) << '\n'; }break;
		}
	}
	return 0;
}