#include <fstream>
#include <vector>

using namespace std;
int N;
vector<int> bit(150001, 0);
vector<int> v;
ifstream cin("aib.in");
ofstream cout("aib.out");
void update(int i, int val)
{
    while(i <= N)
    {
        bit[i] += val;
        i += i & -i;
    }
}
int prefixsum(int i)
{
    int sum=0;
    while( i > 0)
    {
        sum += bit[i];
        i -= i & -i;
    }
    return sum;
}
int rangesum(int i, int j)
{
    return prefixsum(j) - prefixsum(i-1);
}
int cbin(int x)
{
    int st=1, dr=N, mij=-1, aux;
    while (st< dr)
    {
        mij =(st+dr)/2;
        aux = prefixsum(mij);
        if(aux >= x)
            dr = mij;
        else
            st = mij+1;
    }
    return st;
}
int main()
{
    int x, m, op, a, b;
    cin >> N >> m;
    v.push_back(0);
    for(int i=1; i<=N; i++)
    {
        cin >> x;
        v.push_back(x);
        update(i, x);
    }
    for(int i=0; i<m; i++)
    {
        cin >> op;
        if(op == 0){
                cin >> a >> b;
            update(a, b);
        }
        else if(op==1){
                cin >> a >> b;
            cout << rangesum(a,b) << '\n';
        }
        else if(op == 2)
        {
            cin >> a;
            int aux = cbin(a);
            if(rangesum(-1, aux) == a)
                cout << cbin(a) << '\n';
            else
                cout << -1 << '\n';
        }
    }
    return 0;
}