#include <bits/stdc++.h>
#define optim ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define let auto
#define popcount __builtin_popcount
#define ctzll __builtin_ctzll
#define clzll __builtin_clzll

using namespace std;
string filename = "aib";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int sze = 1e5;
int n;
ll aib[sze + 1];

void updateAib(int pos, int x){
    for(int i = pos;i<=n;i += i & -i){
        aib[i]+=x;
    }
}
inline ll queryAib(int pos){
    ll s= 0;
    for(int i = pos;i>0;i -= i & -i){
        s+=aib[i];
    }
    return s;
}


inline int Search(int a, int cnt){
    int x,y; 
    bool ok = true;
    for(int i =1;i<=100000;i<<=1){
        if(aib[i + cnt] == a) return i;
        if(aib[i + cnt] > a){
            y = i;
            x = i>>1;
            ok = false;
            break;
        }
    }
    if(ok) return -1;
    a-=aib[x];
    return Search(a, x);
}




int main()
{
    int m, x;
    fin>>n>>m;
    for(int i = 1;i<=n;++i){
        fin>>x;
        updateAib(i, x);
    }
    int a, b, op;
    while(m--){
        fin>>op;
        if(op == 0){
            fin>>a>>b;
            updateAib(a, b);
        }
        else if(op == 1){
            fin>>a>>b;
            fout<<queryAib(b) - queryAib(a - 1)<<'\n';
        }
        else {
            fin>>a;
            fout<<Search(a, 0)<<'\n';
        }
    }

    return 0;
}