#include <bits/stdc++.h>
#define DIM 2000001
#define int long long

using namespace std;

ifstream fin("aib.in");

ofstream fout("aib.out");

int bit[DIM], v[DIM];

int n, i, Q, task, x, y;

int lsb(int n){

    return (n & -n);
}

void Update(int i, int add){

    for(; i <= n ; i += lsb(i))

        bit[i] += add;

}

int Query(int i){

    int ret = 0;

    for(; i >= 1 ; i -= lsb(i))

        ret += bit[i];

    return ret;

}

int binary_lifting(int target){

    int ret = 0;

    int ans = 0;

    for(i=log2(n);i>=0;i--){

        if(ret + (1 << i) <= n && ans + bit[ret + (1 << i)] <= target){

            ans += bit[ret + (1 << i)];

            ret += (1 << i);

        }

    }

    if(ans == target)

        return ret;

    return -1;

}

int32_t main(){

    fin >> n >> Q;

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

        fin >> v[i];

        Update(i, v[i]);

    }

    while(Q--){

        fin >> task;

        if(task == 0){

            fin >> x >> y;

            Update(x, y);

            v[x] += y;

        }

        if(task == 1){

            fin >> x >> y;

            fout << Query(y) - Query(x - 1) << "\n";

        }

        if(task == 2) {

            fin >> x;

            fout << binary_lifting(x) << "\n";

        }

    }

}