#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in") ;
ofstream fout("aib.out") ;
const int NM=100001 ;
int aib[NM],n,m,x ;
inline int next(int x)
{
    return (x^(x-1))&x ;
}
void insert(int pos,int val)
{
    for(int i=pos; i<=n; i+=next(i)) aib[i]+=val ;
}
int query(int pos)
{
    int s=0 ;
    for(int i=pos; i>0; i-=next(i)) s+=aib[i] ;
    return s ;
}
int bs(int k)
{
    int st=1,dr=n,mij ;
    while(st<=dr)
    {
        mij=(st+dr)>>1 ;
        if(query(mij)==k) return mij ;
        else if(query(mij)>k) dr=mij-1 ;
        else st=mij+1 ;
    }
    return -1 ;
}
int main()
{
    fin>>n>>m ;
    for(int i=1; i<=n; ++i) fin>>x,insert(i,x);
    for(int i=1,op,x,y; i<=m; ++i)
    {
        fin>>op ;
        if(op==0) fin>>x>>y,insert(x,y) ;
        if(op==1) fin>>x>>y,fout<<query(y)-query(x-1)<<'\n';
        if(op==2) fin>>x,fout<<bs(x)<<'\n' ;
    }
    return 0;
}