//#include <iostream>
#include <fstream>

#define zeros(n) (n & -n)

using namespace std;

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

long int n, *c, k, st;

inline int msb(long int n){
	long num = 0;
	if (!n) return -1;
	if (0xFFFF0000 & n)
	{
		n = (0xFFFF0000 & n)>>16;
		num += 16;
	}
	if (0xFF00 & n)
    {
		n = (0xFF00 & n) >> 8;
		num += 8;
	}
	if (0xF0 & n) {
		n = (0xF0 & n) >> 4;
		num += 4;
    }
	if (12 & n)
    {
		n = (12 & n) >> 2;
		num += 2;
	}
	if (2 & n)
    {
		n = (2 & n) >> 1;
		num += 1;
	}
    return 1 << num;
}

void add(long int x, long int y)
{
	while (x <= n)
	{
		c[x] += y;
		x += zeros(x);
	}
}

long int interog(long int x)
{
	
	long int sum = 0;
	while (x > 0)
	{
		sum += c[x];
		x -= zeros(x);
	}
	return sum;
}

int search(int x)
{
	int s;
    
    s = msb(n);
    
    for (int i = 0; s; s >>= 1)
    {
         if (i + s <= n)
         {
            if (x >= c[i + s]) 
            {
                i += s; x -= c[i];
                if (!x) return i;
            }
         }
    }
    
    return -1;
}

int main()
{
	long int x, y, z, t;
	fin >> n >> t; 
	
	c = new long int[n + 1];
	
	for (int i = 1; i <= n; ++i)
	{
		fin >> x;
		add(i, x);
	};
	
	for (int i = 0; i < t; ++i)
	{
		fin >> x;
		if (x == 0)
		{
			fin >> y >> z;
			add(y, z);
		}
		else if (x == 1)
		{
			fin >> y >> z;
			fout << interog(z) - interog(y - 1) << endl;
		}
		else if (x == 2)
		{
			fin >> y;
			fout << search(y) << endl;
		}
	}
	
	return 0;
}