#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define zeros(pos) ((pos^(pos-1))&pos)

using namespace std;

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

const int NMAX = 100005;

int aib[NMAX];

int m, n;

void add(int pos, int val)
{
	for (int i = pos; i <= n; i += zeros(i))
		aib[i] += val;
}

int query(int pos)
{
	int sum = 0;
	for (int i = pos; i > 0; i -= zeros(i))
		sum += aib[i];
	return sum;
}

int main()
{
	int x;
	fin >> n >> m;
	for (int i = 1; i <= n; i++) 
	{
		fin >> x;
		add(i, x);
	}
	while (m--)
	{
		int op, a, b;
		fin >> op;
		if (op == 0)
		{
			fin >> a >> b;
			add(a, b);
		}
		else if (op == 1)
		{
			fin >> a >> b;
			fout << query(b)-query(a-1) << '\n';
		}
		else if (op == 2)
		{
			fin >> a;
			int st = 1;
			int dr = n;
			int med, ans = -1, sum = -1;
			while (st <= dr)
			{
				med = (st + dr) / 2;
				int q = query(med);
				if (q >= a)
				{
					ans = med;
					sum = q;
					dr = med - 1;
				}
				else
					st = med + 1;
			}
			fout << ans << '\n';
		}
	}
	return 0;
}