#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
//ifstream f("file.in");
//ofstream g("file.out");
int n, m, aib[100100],el,i,k,type,a,b;
// We will add val to pos and all the nodes whose intervals incldue pos.
// Note that pos needs to be unsigned because otherwise we will get the negative complement.
void update(int val,unsigned int pos)
{
	while (pos <= n)
	{
		//We get 2's complement to pos,bitwise AND it with pos, and add that to pos and we get the next position.
		aib[pos] += val;
		pos += (~pos + 1)&(pos);
	}
}
int search(unsigned int pos)
{
	int res=0;
	while (pos != 0)
	{
		res += aib[pos];
		pos -= (~pos + 1)&pos;
	}
	return res;
}
int cb(int value)
{
	int l = 1, r = n,mid,res;
	while (l <= r)
	{
		mid = (l + r) / 2;
		res = search(mid);
		if (res == value)
		{
			return mid;
		}
		else
			if (res > value)
			{
				r = mid-1;
			}
			else
			{
				l = mid + 1;
			}
	}
	return -1;
}
int main()
{
	f >> n>>m;
	for (i = 1; i <= n; i++)
	{
		f >> el;
		update(el, i);
	}
	for (k = 1; k <= m; k++)
	{
		f >> type;
		if (type == 0)
		{
			f >> a >> b;
			update(b, a);
		}
		if (type == 1)
		{
			f >> a >> b;
			g << search(b) - search(a-1) << '\n';
		}
		if (type == 2)
		{
			f >> a;
			g << cb(a)<<'\n';
		}
	}
	return 0;
}