#include <iostream>
#include <vector>
#include <string>
#include <fstream>

using namespace std;

#define zeroes(x) ((x^(x-1))&x)

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

int AIB[1000000],n,m;

void update(int x, int q)
{
	for (int i = x; i <= n; i += zeroes(i))
		AIB[i] += q;
}

int sum(int a)
{
	int rez = 0;
	for (int i = a; i > 0; i -= zeroes(i))
	{
		rez += AIB[i];
	}
	return rez;
}


int main()
{
	ios_base::sync_with_stdio(false);
	fin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int x;
		fin >> x;
		update(i, x);
	}

	for (int i = 1; i <= m; i++)
	{
		int t, x, y;
		fin >> t;
		switch (t)
		{
		case 0:
			fin >> x >> y;
			update(x, y);
			break;
		case 1:
			fin >> x >> y;
			fout << sum(y) - sum(x - 1) << '\n';
			break;
		case 2:
			fin >> x;
			int left = 1, right = n, mid;
			bool checked = 0;
			while (left < right)
			{
				mid = (left + right) / 2;
				int sm = sum(mid);
				if (sm == x)
				{
					fout << mid << '\n';
					checked = 1;
					break;
				}
				else
				{
					if (sm < x)left = mid+1;
					else right = mid;
				}

			}
			mid = right;
			int sm = sum(mid);
			if (sm == x && checked == 0)
			{
				fout << mid << '\n';
				checked = 1;
				break;
			}
			if (checked == 0) fout << -1 << '\n';
			break;
		
		}
	}
	
	
}