#include <bits/stdc++.h>
#include <unordered_map>
#define nmax 100005
#define MOD 1999999973
#define INF 2012345678
#define ll long long
using namespace std;
//#define fin cin
//#define fout cout

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

int n, m;
int aib[nmax];

void Update(int p, int y)
{
	while (p <= n)
	{
		aib[p] += y;
		p += (p & (-p));
	}
}

int Query(int p)
{
	int sum;
	sum = 0;
	while (p > 0)
	{
		sum += aib[p];
		p -= (p & (-p));
	}
	return sum;
}

// cel mai din st mij a.i. Query(mij) == x
int CB(int x)
{
	int st, dr, mij, p, sum;
	st = 1; dr = n; p = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		sum = Query(mij);
		if (sum == x)
		{
			p = mij;
			dr = mij - 1;
		}
		else if (sum < x)
			st = mij + 1;
		else
			dr = mij - 1;
	}
	return p;
}

int main()
{
	int i, x, y, t;
	fin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		fin >> x;
		Update(i, x);
	}
	while (m--)
	{
		fin >> t >> x;
		if (t == 0)
		{
			fin >> y;
			Update(x, y);
		}
		else if (t == 1)
		{
			fin >> y;
			fout << Query(y) - Query(x - 1) << "\n";
		}
		else
			fout << CB(x) << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}