#include <iostream>
#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int n,m,aib[100050];

int zeros(int x)
{
    return ( (x ^ (x - 1)) & x );
}

void build()
{
   for(int i = 1 ; i <= n ; i++)
       aib[i+zeros(i)] += aib[i];
}

void Add(int x,int quantity)
{
    for(int i = x ; i <= n ; i += zeros(i) )
        aib[i] += quantity;
}

int Compute(int x)
{
    int ret = 0;
    for(int i = x ; i > 0 ; i -= zeros(i) )
        ret += aib[i];
    return ret;
}

int BinarySearch(int x)
{
    int ret=-1,a=1,b=n,mij,aux;

    while( a <= b )
    {
        mij=(a+b)/2;
        aux = Compute(mij);

        if( aux >= x )
            b = mij-1;

        if( aux <  x )
            a = mij+1;

        if(( aux == x ) && ( ret == -1 || ( ret != -1 && ret > mij ) ) )
            ret = mij;
    }
    return ret;
}

int main()
{
    int q,a,b;
    f>>n>>m;
    for(int i = 1 ; i <= n ; ++i)
        f>>aib[i];
    build(); // O(n)

    for(int i = 1 ; i <= m ; ++i)
    {
       f>>q;
       if( q == 0 )
       {
           f>>a>>b;
           Add(a,b);
       }
       else
       if( q == 1 )
       {
           f>>a>>b;
           g<<Compute(b)-Compute(a-1)<<'\n';
       }
       else
       if( q == 2 )
       {
           f>>a;
           g<<BinarySearch(a)<<'\n';
       }
       /*switch(q)
       {
        case 0 : f>>a>>b; Add(a,b);
        case 1 : f>>a>>b; g<<Compute(b)-Compute(a-1)<<'\n';
        case 2 : f>>a; g<<BinarySearch(a)<<'\n';
       }
       */
    }
    return 0;
}