//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>
#include <fstream>
ifstream cin ("aib.in");ofstream cout ("aib.out");

int aib[100100];

int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << setprecision(10) << fixed;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(NULL));

    int n , m;
    cin>>n>>m;

    for (int i=1; i<=n; i++){
        int nr;
        cin>>nr;
        for (int j=i; j<=n; j+=j&(-j)){
            aib[j] += nr;
        }
    }

    for (int i=1; i<=m; i++){
        int t;
        cin>>t;
        if (t == 0){
            int a , b;
            cin>>a>>b;
            for (int j=a; j<=n; j+=j&(-j)){
                aib[j] += b;
            }
        }
        if (t == 1){
            int a , b;
            cin>>a>>b;
            int A = 0 , B = 0;
            for (int j=a-1; j; j-=j&(-j)){
                A += aib[j];
            }
            for (int j=b; j; j-=j&(-j)){
                B += aib[j];
            }
            cout<<B-A<<'\n';
        }
        if (t == 2){
            int a;
            cin>>a;
            int k = -1 , st = 0 , dr = n;
            while (st <= dr){
                int mij = st + dr;
                mij /= 2;
                int cont = 0;
                for (int j=mij; j; j-=j&(-j)){
                    cont += aib[j];
                }
                if (cont == a){
                    k = mij;
                    break;
                }
                if (cont > a){
                    dr = mij - 1;
                }
                else{
                    st = mij + 1;
                }
            }
            cout<<k<<'\n';
        }
    }


    return 0;
}