#include <fstream>
using namespace std;

const int MAX_N = 100002;

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

inline void Update(int p, int x){
    while(p <= N){
        C[p] += x;

        int tmp = p, k = 0;
        while(tmp){
            if(tmp%2 == 0)
                ++k;
            else break;
            tmp /= 2;
        }

        p += pow[k];
    }
}

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

    while(p > 0){
        Sum += C[p];

        int tmp = p, k = 0;
        while(tmp){
            if(tmp%2 == 0)
                ++k;
            else break;
            tmp /= 2;
        }

        p -= pow[k];
    }

    return Sum;
}

inline int BS(int x){
    int 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 <= 31; ++i)
        pow[i] = pow[i-1] * 2;

    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;
}