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

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

////////////////////////////////

const int MAX = 1e5 + 1;

int aib[MAX] , n , t[MAX] , aux , a , b , m;

////////////////////////////////

int lsb( int x ){

    int i;

    for( i = 0 ; !(x&1) ; i++){

        x >>= 1;
    }

    return (1 << i);
}

void initaib(){

    for(int i = 1 ; i <= n ; i++){

        int x = lsb(i);

        if(i + x <= n){

            t[i] = i + x;

            aib[t[i]] += aib[i];

        }else t[i] = n + 1;
    }

}

void update( int a , int b){

    while( a <= n ){

        aib[a] += b;

        a = t[a];
    }

}

int query( int x ){

    int y = 0;

    while(x){

        int a = lsb(x);

        y += aib[x];

        x -= a;
    }

    return y;
}

int bs( int a ){

    int st = 1;
    int dr = n;

    while(st <= dr){

        int mij = (st + dr) / 2;

        int val = query(mij);

        if(val == a){

            return mij;

        }else if( val < a ){

            st = mij + 1;

        }else dr = mij - 1;

    }

    return -1;

}

int main()
{

    in >> n >> m;

    for(int i = 1 ; i <= n ; i++) in >> aib[i];

    initaib();

    while(m--){

        in >> aux;

        if( aux == 0 ){

            in >> a >> b;

            update(a,b);
        }

        if( aux == 1 ){

            in >> a >> b;

            out << query(b) - query(a-1)  << '\n';
        }

        if( aux == 2 ){

            in >> a;

            out << bs(a) << '\n';
        }
    }

    return 0;
}