#include <bits/stdc++.h>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

const int NMAX = 1e5;
int AIB[NMAX + 5], V[NMAX + 5];
int N, M, op, a, b;

int ub(int x)
{
	return (x & (-x));
}

void add(int x, int y)
{
	for (int i = x; i <= N; i += ub(i))
		AIB[i] += y;
}

int sum(int x)
{
	int rez = 0;
	for (int i = x; i >= 1; i -= ub(i))
		rez += AIB[i];
	return rez;
}

int main()
{
	f >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		f >> V[i];
		add(i, V[i]);
	}
	for (int i = 1; i <= M; i++)
	{
		f >> op;
		if (op == 0)
		{
			f >> a >> b;
			add(a, b);
		}
		else
		if (op == 1)
		{
			f >> a >> b;
			g << sum(b) - sum(a - 1) << '\n';
		}
		else
		if (op == 2)
		{
			f >> a;
			int s = 0, poz = 0;
			for (int b = 17; b >= 0; b--)
			{
				if (poz + (1 << b) <= N && s + AIB[poz + (1 << b)] < a)
				{
					s += AIB[poz + (1 << b)];
					poz += (1 << b);
				}
			}
			if (poz + 1 > N || sum(poz + 1) != a)
					g << -1 << '\n';
				else
					g << poz + 1 << '\n';
		}
	}
	f.close();
	g.close();
    return 0;
}