#include <bits/stdc++.h>
#define steps(x) (x&(-x))
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
int aib[100005],n;

void add(int v, int x){
    int i;
    for(i=x;i<=n;i+=steps(i)){
        aib[i]+=v;
    }
}

int query(int x){
    int i;
    int sol=0;
    for(i=x;i>0;i-=steps(i)){
        sol+=aib[i];
    }
    return sol;
}

int bs(int val){
    int s,d,m,x;
    s=1;d=n;
    while(s<=d){
        m=(s+d)/2;
        x=query(m);
        if(x==val){
            return m;
        }
        else{
            if(x>val){
                d=m-1;
            }
            else{
                s=m+1;
            }
        }
    }
    return -1;
}
int main()
{int m,s,d,i,t;
in>>n>>m;
for(i=1;i<=n;i++){
    in>>t;
    add(t,i);
}
for(i=1;i<=m;i++){
    in>>t;
    if(t==0){
        in>>s>>d;
        add(d,s);
    }
    if(t==1){
        in>>s>>d;
        out<<query(d)-query(s-1)<<'\n';
    }
    if(t==2){
        in>>s;
        out<<bs(s)<<'\n';
    }
}
for(i=1;i<=n;i++){
    out<<aib[i]<<" ";
}
    return 0;
}