#include <bits/stdc++.h>
#define N 100007
#define pb push_back
using namespace std;

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

int n,q;
vector<int>aib(N+1,0);

void Update_AIB(int poz,int val)
{
    while( poz<=n )
    {
        aib[poz]+=val;
        poz+= ( poz&(-poz) );
    }
}

int Suma_AIB(int poz)
{
    int sum=0;
    while( poz>=1 )
    {
        sum+=aib[poz];
        poz-= (poz&(-poz));
    }
    return sum;
}

void T2(int x)
{
    int st=1,dr=n,poz=-1;
    while( st<=dr )
    {
        int mij=(st+dr)/2;
        int s=Suma_AIB(mij);
        if( s>=x )
        {
            if( s==x )poz=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout << poz << "\n";
}

int main()
{
    fin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin >> x;
        Update_AIB(i,x);
    }
    for(int i=1;i<=n;i++)cout << aib[i] << " ";

    for(int i=1;i<=q;i++)
    {
        int task;
        fin >> task ;
        if( !task )
        {
            int poz,val;
            fin >> poz >> val;
            Update_AIB(poz,val);
        }
        if( task==1 )
        {
            int st,dr;
            fin >> st >> dr;
            fout << Suma_AIB(dr)-Suma_AIB(st-1) << "\n";
        }
        if( task==2 )
        {
            int val;
            fin >> val;
            T2(val);
        }
    }
    fin.close();
    fout.close();
    return 0;
}