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

FILE *fout = fopen("aib.out", "w") ;

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 OutputParsing {
private :
        static const int SIZE = (1 << 20) ;
        char outBuffer[SIZE] ;
        int outputSize ;
        __attribute__ ( (always_inline)) int numberDigits(int x) {
                int digits = x > 999999999 ? 11 :
                             x > 99999999  ? 10 :
                             x > 9999999   ? 9  :
                             x > 999999    ? 8  :
                             x > 99999     ? 7  :
                             x > 9999      ? 6  :
                             x > 999       ? 5  :
                             x > 99        ? 4  :
                             x > 9         ? 3  : 2 ;
                return digits ;
        }
public :
        FILE *output_file ;
        OutputParsing() {}
        OutputParsing (const char *file_name) {
                output_file = fopen (file_name, "wb") ;
                outputSize = -1 ;
        }
        __attribute__ ( (always_inline)) InputReader &operator << (int val) {
                if (val == -1) {
                        outBuffer[++ outputSize] = 45 ;
                        outBuffer[++ outputSize] = 49 ;
                        outBuffer[++ outputSize] = 10 ;
                } else {
                        int digits = numberDigits(val) ;
                        for (int i = digits ; -- i ; val /= 10) {
                                outBuffer[outputSize + i] = val % 10 + 48 ;
                        }
                        outBuffer[outputSize = outputSize + digits] = 10 ;
                }
        }
        __attribute__ ( (always_inline)) void sflush() {
                for (int i = 0 ; i < outputSize ; ++ i) {
                        fputc(outBuffer[i], fout) ;
                }
        }
};

class BinaryIndexedTree {
private :
        std::vector<int> aib ;
        static const int MAXVAL = (1 << 30) ;
        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 (MAXVAL) ; 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 ;
        }
};

InputReader in ("aib.in") ;
OutputParsing out ("aib.out") ;

int main() {
        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)) ;
                } else {
                        in >> a ;
                        out << (aib.BinarySearch (a)) ;
                }
        }
        out.sflush() ;
}