//Arbori indexati binar
#include<iostream>
#include<fstream>
#define nmax 100001
using namespace std;

int m;

int getParent(int index)
{
    return index-(index & -index);
}

int getNext(int index)
{
    return index+(index & -index);
}

void update(int BITree[],int n,int index,int val)
{
    index++;
    while(index<=n)
    {
        BITree[index]+=val;
        index=getNext(index);
    }

}

int *constructBITree(int arr[],int n)
{
    int *BITree=new int[n+1];
    for(int i=0;i<=n;i++)
        BITree[i]=0;
    //Arborele indexat binar are in plus nodul "dummy" 0, ca radacina (din constructia pe biti)
    for(int i=0;i<n;i++)
        update(BITree,n,i,arr[i]);
    return BITree;
}

int getSum(int BITree[],int index)
{
    int sum41=0;
    //fan punk rock ?
    ++index;
    //indexul din arbore este cu o unitate mai mare decat cel din vector4
    while(index>0)
    {
        sum41+=BITree[index];
        index=getParent(index);
    }
    return sum41;

}

int bs(int BITree[],int n,int st,int dr,int val)
{
    //cout<<st<<' '<<dr<<' ';
    if(dr<=0 || st>n) return -1;
    else
    {
    int mid=(st+dr)>>1,x=getSum(BITree,mid-1);
    if(x==val) return mid;
    else
        if(x<val)
        bs(BITree,n,mid+1,dr,val);
        else
        bs(BITree,n,st,mid-1,val);
    }
}

void read()
{
    int n,i,c,a,b,ins,BITree[nmax];
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>m;
    //v[0.....n-1]
    //BITree[0.....n]
    for(i=0;i<n;i++)
        {fin>>ins;
        update(BITree,n,i,ins);
        }
    //int *BITree=constructBITree(v,n);
    //cout<<getSum(BITree,4)<<' ';
    for(i=1;i<=m;i++)
    {
        fin>>c;
        if(!c)
        {
            fin>>a>>b;
            update(BITree,n,a-1,b);
        }
        else
            if(c==1)
        {
            fin>>a>>b;
            //cout<<a<<b;
            fout<<getSum(BITree,b-1)-getSum(BITree,a-2)<<'\n';
        }
        else
            {
                fin>>a;
                //pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact a.
                //numerele fiind naturale, elementele din getSum(BITree) sunt ordonate crescator
                fout<<bs(BITree,n,1,n,a)<<'\n';
                //for(i=0;i<=n;i++)
                   // cout<<BITree[i]<<' ';
               // cout<<endl;
                //cout<<"coapte!"<<'\n';
            }
    }
    fin.close();
    fout.close();
}

int main()
{
    read();
}