//#include <iostream>
#include <fstream>

using namespace std;

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

long int n, *c;

void add(long int x, long int y)
{
	while (x <= n)
	{
		c[x] += y;
		x += (x & -x);
	}
}

long int interog(long int x, long int y)
{
	if (x != 1) return interog(1, y) - interog(1, x - 1);
	
	long int sum = 0;
	while (y > 0)
	{
		sum += c[y];
		y -= (y & -y);
	}
	return sum;
}

int search(int x, int st, int dr)
{
	int m = (st + dr) / 2;
	int k = interog(1, m);
	if (k == x) return m;
	if (st == dr) return -1;
	if (k < x) return search(x, m + 1, dr);
	if (k > x) return search(x, st, m);
}

int main()
{
	long int x, y, z, t;
	fin >> n >> t; 
	
	c = new long int[n + 1];
	
	for (int i = 1; i <= n; ++i)
	{
		fin >> x;
		add(i, x);
	};
	
	for (int i = 0; i < t; ++i)
	{
		fin >> x;
		if (x == 0)
		{
			fin >> y >> z;
			add(y, z);
		}
		if (x == 1)
		{
			fin >> y >> z;
			fout << interog(y, z) << endl;
		}
		if (x == 2)
		{
			fin >> y;
			fout << search(y, 1, n) << endl;
		}
	}
	
	return 0;
}