#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
using namespace std;

int f[100000];
int tree[150000];
int n;

void update(int idx ,int val){
    while (idx <= n){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

int cumulative(int idx){
    int sum=0;
    while(idx){
        sum = sum + tree[idx];
        idx = idx - (idx & -idx);
    }
    return sum;
}

int binSearch(int s, int left, int right){
    int mid = (left+right)/2;
    int t = cumulative(mid);

    if(left == right)
        if(s == t)
            return left;
        else
            return -1;

    if(s > t)
        return binSearch(s,mid + 1,right);
    else if(s < t)
        return binSearch(s,left,mid);
    else
        return mid;

}

int main()
{
    int m,i,x,y,z;
    fin >> n >> m;
    for(i=1;i<=n;++i)
        fin >> f[i],
        update(i,f[i]);

    for(i=1;i<=m;++i){
        fin >> x;
        if(x == 0)
            fin >> y >> z,
            update(y,z);
        else if(x == 1)
            fin >> y >> z,
            fout << cumulative(z) - cumulative(y-1) << '\n';
        else
            fin >> y,
            fout << binSearch(y,1,n) <<'\n';
    }




    return 0;
}