#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int aib[100001],n,m;
void add(int poz, int x)
{
   while(poz<=n)
   {
       aib[poz]+=x;
       poz+=(poz&(-poz));
   }
}
int suma(int poz)
{
   int s=0;
   while(poz>0)
   {
       s+=aib[poz];
       poz-=(poz&(-poz));
   }
   return s;
}
void citire()
{
    int x;
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>x;
        add(i,x);
    }
}
int pozitie(int k)
{
   int step, ans;
	for(step = 1; step <= n; step *= 2);
	for(ans = 0; step; step /= 2)
		if(step + ans <= n and k>=aib[step + ans])
			{ans += step;
			 k-=aib[ans];
			 if(k==0) return ans;}
	return -1;
}
int main()
{
    int a,b,op;
    citire();
    for(int i=1;i<=m;i++)
    {
        f>>op;
        if(op==0)
        {
            f>>a>>b;
            add(a,b);
        }
        if(op==1)
        {
            f>>a>>b;
            a=suma(a-1);
            b=suma(b);
            g<<b-a<<"\n";
        }
        if(op==2)
        {
            f>>a;
            g<<pozitie(a)<<"\n";
        }
    }
    return 0;
}