#include <fstream>
using namespace std;

const int MAX_N = 100002;

unsigned int N, M;
unsigned int C[MAX_N], Nr[MAX_N], pow[35];

inline void Update(unsigned p, unsigned x){
    while(p <= N){
        C[p] += x;
        p += pow[Nr[p]];
    }
}

inline unsigned Query(unsigned p){
    unsigned Sum = 0;

    while(p > 0){
        Sum += C[p];
        p -= pow[Nr[p]];
    }

    return Sum;
}

inline int BS(unsigned x){
    unsigned left = 0, right = N+1, mid = 0;

    while(left < right){
        mid = (left + right)/2;
        if(Query(mid) > x)
            right = mid;
        else left = mid+1;
    }

    if(Query(left-1) != x)
        return-1;
    return left-1;
}

int main(){
    ifstream f("aib.in");
    ofstream g("aib.out");

    pow[0] = 1;
    for(int i = 1; i <= 32; ++i)
        pow[i] = pow[i-1] * 2;

    for(int i = 1; i < MAX_N; ++i){
        unsigned tmp = i, k = 0;
        while(tmp){
            if(tmp%2 == 0)
                ++k;
            else tmp = 0;
            tmp /= 2;
        }
        Nr[i] = k;
    }

    f >> N >> M;
    for(int i = 1, x = 0; i <= N; ++i){
        f >> x;
        Update(i, x);
    }

    for(int q = 1; q <= M; ++q){
        int t, p, x, a, b, Res;

        f >> t;

        if(!t){
            f >> p >> x;
            Update(p, x);
        }
        else if(t == 1){
            f >> a >> b;
            Res = Query(b) - Query(a-1);
        }
        else{
            f >> x;
            Res = BS(x);
        }

        if(t >= 1)
            g << Res << '\n';
    }

    f.close();
    g.close();

    return 0;
}