#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <queue>
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <iomanip>
#include <stack>
#include <climits>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;

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

int n, aib[100002], m;

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 a)
{
	int st, dr, mij, pos;
	st = 1; dr = n; pos = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		int s = Query(mij);
		if (s == a)
		{	
			pos = mij;
			dr = mij - 1;
		}
		else if (s < a) st = mij + 1;
		else dr = mij - 1;
	}
	return pos;
}

int main()
{
	int i, x, op, a, b;
	fin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		fin >> x;
		Update(i, x);
	}
	while (m--)
	{
		fin >> op;
		if (op == 0)
		{
			fin >> a >> b;
			Update(a, b);
		}
		else if (op == 1)
		{
			fin >> a >> b;
			fout << Query(b) - Query(a - 1) << "\n";
		}
		else /// op == 2
		{
			fin >> a;
			fout << CB(a) << "\n";
		}
	}
	return 0;
}