#include<fstream>
using namespace std;

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

int A[100010];
int AIB[100010],N,Q;

void update(int x,int val)
{
	for (;x <= N;x += (x & (-x)))
		AIB[x] += val;
}

int query(int x)
{
	int s = 0;
	for (;x;x-= (x & (-x)))
		s+=AIB[x];
	return s;
}

int main()
{
	in >> N >> Q;
	for (int i = 1;i <= N;++i)
	{
		in >> A[i];
		update(i,A[i]);
	}
	for (int i = 1;i <= Q;++i)
	{
		int op,a,b;
		in >> op;
		switch (op)
		{
			case 0:
				in >> a >> b;
				update(a, b);
				break;
			case 1:
				in >> a >> b;
				out << query(b) - query(a - 1) << '\n';
				break;

			case 2:
				in >> a;
				int l = 1, r = N,mid;
				int pos = -1;
				while (l <= r)
				{
					mid = (l + r) >> 1;
					if (query(mid) == a)
					{
						pos = mid;
						r = mid - 1;
					}
					else if (query(mid) > a)
						r = mid - 1;
					else
						l = mid + 1;
				}
				out << pos<<'\n';
				break;
		}
	}
	return 0;
}