/*
ID: Sho10
LANG: C++
TASK:
*/
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,m,a[500005],tree[500005];
ll sum(ll);
void add(ll,ll);
ll bs(ll,ll,ll);
int32_t main(){
    ifstream cin("aib.in");
    ofstream cout("aib.out");
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
    cin>>a[i];
    add(i,a[i]);
}
while(m--){
    ll sho,boss,purice;
    cin>>sho;
    if(sho==0){
        cin>>boss>>purice;
        add(boss,purice);
    }else if(sho==1){
        cin>>boss>>purice;
    cout<<sum(purice)-sum(boss-1)<<endl;
    }else if(sho==2){
        cin>>boss;
    cout<<bs(boss,1LL,n)<<endl;
}
}
}
ll sum(ll k){
ll ans=0;
while(k>=1){
        ans=ans+tree[k];
k=k-(k&-k);
}
return ans;
}
void add(ll k,ll x){
    while(k<=n){
        tree[k]=tree[k]+x;
        k=k+(k&-k);
    }
}
ll bs(ll s1,ll l,ll r){
    while(l<=r){
ll mid=(l+r)/2;
if(sum(mid)==s1){
    return mid;
}else if(sum(mid)<s1){
    l=mid+1;
}else if(sum(mid)>s1){
r=mid-1;
}
    }
return -1;
}