#include <cstdio>

const int MAX_N(100001);

int n, m;

int bit [MAX_N];

inline int lsb (int x)
{
	return x & (-x);
}

inline void update (int p, int v)
{
	bit[p] += v;
	p += lsb(p);
	while (p <= n)
	{
		bit[p] += v;
		p += lsb(p);
	}
}

inline int query (int p)
{
	int sum(bit[p]);
	p -= lsb(p);
	while (p)
	{
		sum += bit[p];
		p -= lsb(p);
	}
	return sum;
}

inline int min (int a, int b)
{
	return a < b ? a : b;
}

inline int search (int x)
{
	int p(n + 1), left(0), right(n + 1), sum(query(n)), b(n);
	if (sum == x)
		p = n;
	while (b)
	{
		b = (left + right) >> 1;
		sum = query(b);
		if (sum > x)
		{
			if (right > b)
				right = b;
			--b;
		}
		else if (sum == x)
		{
			p = min(p, b);
			left = b;
			--b;
		}
		else
		{
			if (left < b)
				left = b;
			++b;
		}
		if (b <= left || b >= right)
			break;
	}
	if (p <= n)
		return p;
	return -1;
}

inline void read (void)
{
	std::scanf("%d %d\n",&n,&m);
	int x;
	for (int i(1) ; i <= n ; ++i)
	{
		std::scanf("%d",&x);
		update(i,x);
	}
}

int main (void)
{
	std::freopen("aib.in","r",stdin);
	std::freopen("aib.out","w",stdout);
	read();
	int o, a, b;
	while (m)
	{
		std::scanf("%d",&o);
		if (o == 2)
		{
			std::scanf("%d",&a);
			std::printf("%d\n",search(a));
		}
		else if (o == 1)
		{
			std::scanf("%d %d",&a,&b);
			std::printf("%d\n",query(b) - query(a - 1));
		}
		else
		{
			std::scanf("%d %d",&a,&b);
			update(a,b);
		}
		--m;
	}
	std::fclose(stdout);
	std::fclose(stdin);
	return 0;
}