#include<fstream>
#define zeros(x) (x&(-x))
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,tip,x,y,AIB[100005];
void Add(int poz, int val)
{
    while(poz<=n) {AIB[poz]+=val; poz+=zeros(poz);}
}
int Query(int poz)
{
    int s=0;
    while(poz){s+=AIB[poz]; poz-=zeros(poz);}
    return s;
}
int Search(int val)
{
    int v,st,dr,m;
    st=1; dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        v=Query(m);
        if(v==val) return m;
        if(v<val) st=m+1;
        else dr=m-1;
    }
    return -1;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++) {f>>x; Add(i,x);}
    for(int i=1;i<=m;i++)
    {
        f>>tip;
        switch(tip)
        {
            case 0: {f>>x>>y; Add(x,y); break;}
            case 1: {f>>x>>y; g<<Query(y)-Query(x-1)<<'\n'; break;}
            case 2: {f>>x; g<<Search(x)<<'\n'; break;}
        }
    }
    g.close();
    return 0;
}