#include <fstream>

using namespace std;

const int NMAX = 100005;
int n, m, aib[NMAX];

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

void Update(int pos, int val)
{
	while (pos <= n)
	{
		aib[pos] += val;
		pos += lsb(pos);
	}
}

int Query(int pos)
{
	int ret = 0;
	while (pos >= 1)
	{
		ret += aib[pos];
		pos -= lsb(pos);
	}
	return ret;
}

int BinarySearch(int val)
{
	int left = 1, right = n, mid, p;
	while (left <= right)
	{
		mid = (left + right) / 2;
		int aux = Query(mid);
		if (aux == val)
			return mid;
		if (aux < val)
			left = mid + 1;
		else
			right = mid - 1;
	}
	return -1;
}

int main()
{
	ifstream fin("aib.in");
	ofstream fout("aib.out");
	fin >> n >> m;
	for (int i = 1;i <= n;++i)
	{
		int val;
		fin >> val;
		Update(i, val);
	}
	for (int i = 1;i <= m;++i)
	{
		int op, a, b;
		fin >> op;
		if (op == 0)
		{
			fin >> a >> b;
			Update(a, b);
		}
		if (op == 1)
		{
			fin >> a >> b;
			fout << Query(b) - Query(a - 1) << "\n";
		}
		if (op == 2)
		{
			fin >> a;
			fout << BinarySearch(a) << "\n";
		}
	}
	return 0;
}