//https://infoarena.ro/problema/aib

#include <fstream>
#include <vector>

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

using namespace std;

class ArbIB
{
	vector<int> v;
	int size_of_array;
public:
	ArbIB(int size)
	{
		size_of_array = size;
		v.resize(size + 1,0);
	}
	void Update(int index, int val)	
	{
		for (int i = index; i <= size_of_array; i += (i & -i))
			v[i] += val;
	}
	int Querry(int st, int dr)
	{
		return QuerryUtil(dr) - QuerryUtil(st - 1);
	}
	int Search(int k)
	{
		int st = 0, dr = size_of_array, mid, sum;
		while (st <= dr)
		{
			mid = (st + dr) / 2;
			sum = QuerryUtil(mid);
			if (sum == k)
				return mid;
			if (sum > k)
				dr = mid - 1;
			else
				st = mid + 1;
		}
		return -1;
	}
private:
	int QuerryUtil(int dr)
	{
		int sum = 0;
		for (int i = dr; i >= 1; i -= (i & -i))
			sum += v[i];
		return sum;
	}
};
int main()
{
	int n, m, x, cer, a, b;
	fin >> n >> m;
	ArbIB AIB(n);
	for (int i = 1; i <= n; ++i)
	{
		fin >> x;
		AIB.Update(i, x);
	}

	while (m--)
	{
		fin >> cer;
		if (cer == 0)
		{
			fin >> a >> x;
			AIB.Update(a, x);
		}
		else if (cer == 1)
		{
			fin >> a >> b;
			fout << AIB.Querry(a, b) << '\n';
		}
		else if (cer == 2)
		{
			fin >> x;
			fout << AIB.Search(x) << '\n';
		}
	}
}