#include <fstream>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <cstring>
#include <map>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define oo 2000000
#define MOD 1000000007
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100005],n,m,cer,x,y;
void Update(int p, int x)
{
	while (p <= n)
	{
		aib[p] += x;
		p += (p & -p);
	}
}

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

int CB(int k)
{
	int st = 1, dr = n,rez=0;
	while (st <= dr)
	{
		int mij = (st + dr) / 2;
		int x = Query(mij);
		if (x == k)
		{
			rez = mij;
			dr = mij - 1;
		}
		else if (x > k)
		{
			dr = mij - 1;
		}
		else
			st = mij + 1;
	}
	return  rez;
}
int main()
{
	fin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		fin >> x;
		Update(i, x);
	}
	while (m--)
	{
		fin >> cer;
		if (cer == 0)
		{
			fin >> x >> y;
			Update(x, y);
		}
		else if (cer == 1)
		{
			fin >> x >> y;
			fout << Query(y) - Query(x-1) << endl;

		}
		else
		{
			fin >> x;
			fout<<CB(x)<<endl;
		}
	}


}