#include <fstream>
using namespace std;


int t[100001];

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

int LSB(int x)
{
	return x&(x - 1) ^ x;
}

int MSB(int x)
{
	int aux = 1;
	while (x!=0)
	{
		x>>= 1; 
		aux <<= 1;
	}
	return aux >> 1;
}

void increment(int p, int val,int n)
{
	while (p <= n)
	{
		t[p] += val;
		p += LSB(p);
	}
}



/*void init(int n)
{
	for (int i = 1; i <= n; i++)
	{
		t[i] = 0;
	}
	for (int i = 1; i <= n; i++)
	{
		t[i] += a[i];
		int k = i+ bit(i);
		while (k <= n)
		{
			t[k] += a[i];
			k += bit(k);
		}
	}
}*/

int sum(int i, int sf)
{
	if (i != 1)
		return sum(1, sf) - sum(1, i - 1);
	int s =0;
	while (sf != 0)
	{
		s += t[sf];
		sf -= LSB(sf);
	}
	return s;
}

int posk(int s,int n)
{
	bool g = 0;
	int m = MSB(n);
	int sc = t[m];
	while (!g)
	{
		if (m == 0)
			return -1;
		if (sc == s)
			return m;
		else
		{
			if (sc > s)
			{
				int aux = m;
				m^=LSB(m)|(LSB(m)>>1);
				sc -= t[aux]-t[m];
				if (aux != LSB(aux) && m == LSB(aux))
					return -1;
			}
			else
			{
				if (m == (m | m >> 1))
					return -1;
				m |= m >> 1;
				sc += t[m];
			}
		}
	}
}



int main()
{
	int n;
	int m;
	fin >> n>>m;
	for (int i = 1; i <= n; i++)
	{
		int aux;
		fin >> aux;
		increment(i, aux, n);
	}
	for (int i = 1; i <= m; i++)
	{
		int aux;
		fin >> aux;
		if (aux == 0)
		{
			int poz; int x;
			fin >> poz >> x;
			increment(poz, x,n);
		}
		if (aux == 1)
		{
			int inc; int sf;
			fin >> inc >> sf;
			fout << sum(inc, sf) << '\n';
		}
		if (aux == 2)
		{
			int k;
			fin >> k;
			fout <<posk(k,n)<<'\n';
		}

	}
}