#include <fstream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
const int mxN = 1e5;
int aib[mxN+1];
int n, m,x;
int ub(int x)
{
    return (x & (-x));
}
void add(int poz, int val)
{
    for(int i = poz;i<=n;i+=ub(i))
        aib[i]+=val;
}
int sum(int x)
{
    int sol = 0;
    for(int i = x;i>0;i-=ub(i))
        sol+=aib[i];
    return sol;
}
int sum(int l, int r)
{
    return sum(r) - sum(l-1);
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i<=n;i++)
        cin >> x, add(i,x);
    for(int i = 1;i<=m;i++)
    {
        int op;
        cin >> op;
        if(op == 0)
        {
            int a, b;
            cin >> a >> b;
            add(a,b);
        }
        if(op == 1)
        {
            int a , b;
            cin >> a >> b;
            cout << sum(a,b) << '\n';
        }
        if(op == 2)
        {
            int a; cin >> a;
            int l = 1, r = n , mid, sol = -1;
            while(l<=r)
            {
                mid = (l + r) / 2;
                if(sum(mid) >= a)
                    sol = mid, r = mid-1;
                else l = mid+1;
            }
            cout << sol << '\n';
        }
    }
    return 0;
}