#include <bits/stdc++.h>
#pragma GCC optimize ("O3")

std::fstream out ("aib.out", std::ios::out) ;

class InputReader {
private:
        FILE *input_file ;
        static const int SIZE = 1 << 17 ;
        int point ;
        char buffer[SIZE] ;
        __attribute__ ( (always_inline)) void advance() {
                ++ point ;
                if (point == SIZE) {
                        point = 0 ;
                        fread (buffer, SIZE, 1, input_file) ;
                }
        }
public:
        InputReader() {}
        InputReader (const char *file_name) {
                input_file = fopen (file_name, "r") ;
                point = 0 ;
                fread (buffer, SIZE, 1, input_file) ;
        }
        __attribute__ ( (always_inline)) InputReader &operator >> (int &n) {
                for ( ; !isdigit(buffer[point]) ; advance()) ;
                n = 0 ;
                for ( ; isdigit(buffer[point]) ; advance()) {
                        n = n * ((1 << 3) + (1 << 1)) + buffer[point] - '0' ;
                }
                return *this ;
        }
} ;

class BinaryIndexedTree {
private :
        std::vector<int> aib ;
        int sz ;
public :
        __attribute__ ( (always_inline)) BinaryIndexedTree (int _ = 0) {
                this ->sz = _ ;
                aib.resize (sz + 1) ;
        }
        __attribute__ ( (always_inline)) void update (int poz, int val) {
                for (int i = poz ; i <= sz ; i += (i & (-i))) {
                        aib.at (i) += val ;
                }
        }
        __attribute__ ( (always_inline)) int query (int poz) {
                int ret (0) ;
                for (int i = poz ; i > 0 ; i -= (i & (-i))) {
                        ret += (int) aib.at (i) ;
                }
                return ret ;
        }
        __attribute__ ( (always_inline)) int BinarySearch (int val) {
                int ret (0) ;
                for (int step (1 << 30) ; step && val ; step >>= 1) {
                        if (ret + step <= sz && aib[ret + step] <= val) {
                                val -= aib.at (ret + step) ;
                                ret |= step ;
                                if (!val) {
                                        return ret ;
                                }
                        }
                }
                return -1 ;
        }
};

int main() {
        InputReader in ("aib.in") ;
        int n, m ;
        in >> n >> m ;
        std::vector<int> v(n + 1) ;
        BinaryIndexedTree aib (n) ;
        int val, type, a, b ;
        for (int i = 1 ; i <= n ; ++ i) {
                in >> v[i] ;
                aib.update (i, (int) v.at(i)) ;
        }
        for (int i = 1 ; i <= m ; ++ i) {
                in >> type ;
                if (type == 0) {
                        in >> a >> b ;
                        aib.update (a, (int) b) ;
                } else if (type == 1) {
                        in >> a >> b ;
                        out << aib.query (b) - aib.query (a - 1) << '\n' ;
                } else {
                        in >> a ;
                        out << aib.BinarySearch (a) << '\n' ;
                }
        }
}