#include <bits/stdc++.h>

using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
const int NMAX=1e6;
long long aib[NMAX+1], n, m;
int max_p2;
void fenwick_add(int pos, int val)
{
    while(pos<=n)
    {
        aib[pos] += val;
        pos += (pos & -pos);
    }
}

long long fenwick_sum(int pos)
{
    int ans=0;
    for(; pos>0; pos-=pos&(-pos))
        ans+=aib[pos];
    return ans;
}
long long fenwick_range_sum(int from, int to)
{
    return fenwick_sum(to) - fenwick_sum(from - 1);
}
int fenwick_bin_search(long long sum)
{
int ans=0,curr_sum=0;
    for(int step=(1<<30); step>0; step>>=1)
        if(ans+step<=n && curr_sum+aib[ans+step]<sum)
        {
            ans+=step;
            curr_sum+=aib[ans];
        }
    if(ans+1>n || fenwick_sum(ans+1)!=sum)
        return -1;
    return ans+1;
}

int main()
{
    int op, x, y;
    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        in>>x;
        fenwick_add(i, x);
    }
    max_p2 = n;
    while (max_p2 & (max_p2 - 1))
    {
        max_p2 &= (max_p2 - 1);
    }
    for(int i=1; i<=m; i++)
    {
        in>>op;
        if(op==0)
        {
            in>>x>>y;
            fenwick_add(x, y);
        }
        if(op==1)
        {
            in>>x>>y;
            out<<fenwick_range_sum(x, y)<<'\n';
        }
        if(op==2)
        {
            in>>x;
            out<<fenwick_bin_search(x)<<'\n';
        }
    }
}