#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=1e5;

int a[NMAX], n, m;
int bit[NMAX];


void update(int poz, int x){
    for(;poz<=n; poz+=((~poz)+1)&poz){
        bit[poz]+=x;
    }
}

int sum(int poz){
    int ans=0;
    // for(;poz>0;poz=poz&(poz-1)){
    for(;poz>0;poz-=((~poz+1)&poz)){
        ans+=bit[poz];
    }
    return ans;
}

int search(int x){
    int ans=-1;
    int l=1, r=n;
    while(l<=r){
        int mid=(l+r)/2;
        int s=sum(mid);
        if(s==x){
            ans=mid;
            break;
        }
        if(s<x) l=x+1;
        else r=x-1;
    }
    return ans;
}

int main() {
    fin>>n>>m;
    for(int i=1;i<=n;++i)
        fin>>a[i], update(i,a[i]);
    for(int i=1;i<=m;++i){
        int k, x,y;
        fin>>k>>x;
        if(k<=1){
            fin>>y;
            if(k==0){
                update(x,y);
            }
            else {
                fout<<sum(y)-sum(x-1);
            }
        }
        else{
            fout<<search(x);
        }
        if(k==0) goto asd;
        fout<<"\n";
        asd:;
    }
    for(int i=1;i<=n;++i)
        cout<<bit[i]<<" ";
}