#include <bits/stdc++.h>
#define N 100008

using namespace std;


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



int a[N],aib[N];
int n,q;

int ub(int x)
{
    return x&(-x);
}

void AIB_Update(int poz,int val)
{
    if( poz>n )return ;
    aib[ poz ]+= val;
    AIB_Update( poz+ub(poz),val );
}

int AIB_Query(int poz)
{
    if( poz<=0 )return 0;
    return aib[poz]+ AIB_Query( poz-ub(poz) );
}

int main()
{
    fin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
        AIB_Update( i,a[i] );
    }
    for(int i=1;i<=q;i++)
    {
        int task,x,y;
        fin >> task;
        if( task == 0 )
        {
            fin >> x >> y;
            AIB_Update(x,y);
        }
        if( task == 1 )
        {
            fin >> x >> y;
            fout << AIB_Query(y)-AIB_Query(x-1)<< "\n";
        }
        if( task == 2 )
        {
            fin >> x;
            int st=1,dr=n,poz=-1;
            while( st<=dr )
            {
                int mij=(st+dr)/2;
                if( AIB_Query(mij)>=x )
                {
                    poz=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            fout << poz << "\n";
        }
    }


    return 0;
}