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

using namespace std;

#define NMAX 100001
#define zeros(x) ((x ^ (x - 1)) & x)
#define min(a, b) (a < b) ? a : b

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

int n, m;
int AIB[NMAX] = { 0 };

void Add(int index, int value)
{
	for (index; index <= n; index += zeros(index))
	{
		AIB[index] += value;
	}
}

int Compute(int index)
{
	int ret = 0;
	for (index; index > 0; index -= zeros(index))
	{
		ret += AIB[index];
	}
	return ret;
}

int Search(int value)
{
	int left = 1, right = n, middle;
	int currSum = 0;
	while (left <= right)
	{
		middle = (left + right) / 2;
		currSum = Compute(middle);
		if (value == currSum)
		{
			return middle;
		}
		if (value < currSum)
		{
			right = middle - 1;
		}
		else if (value > currSum)
		{
			left = middle + 1;
		}
	}
	return -1;
}

void Read(void)
{
	fin >> n >> m;
	int prop;

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

	int a, b, operation , index;
	for (int j = 0; j < m; j++)
	{
		fin >> operation;
		if (operation == 2)
		{
			fin >> a;
		}
		else
		{
			fin >> a >> b;
		}

		switch (operation)
		{
		case 0:
			Add(a, b);
			break;
		case 1:
			fout << Compute(b) - Compute(a - 1) << '\n';
			break;
		case 2:
			fout << Search(a) << '\n';
			break;
		}
	}
}

int main(void)
{
	Read();
	return 0;
}