#include <iostream>
#include <fstream>

using namespace std;
long long int aib[100005];
long long int rlsb(int x)
{
    return (x&(x-1));
}
long long int alsb(int x)
{
    return x+(x&-x);
}
void update(int poz, long long int val, long long int n)
{
    while (poz<=n)
    {
        aib[poz]=0LL+aib[poz]+val;
        poz=alsb(poz);
    }
}
long long int query (int poz)
{
    long long int sum=0;
    while (poz>0)
    {
        sum+=aib[poz];
        poz=rlsb(poz);
    }
    return sum;
}
long long int cautbin (long long int val, int n)
{
    long long int pas=1<<20;
    long long int poz=0;
    long long int sum=0;
    while (pas>0)
    {
        if (0LL+poz+pas<=n&&0LL+sum+aib[poz+pas]<=val)
        {
            poz=poz+pas;
            sum=0LL+sum+aib[poz];
        }
        pas/=2;
    }
    if (sum==val)
    return poz;

    return -1;
}
int main()
{
    ifstream cin ("aib.in");
    ofstream cout ("aib.out");
    long long int n, q, cer, a, b;
    cin>>n>>q;
    for (int i=1; i<=n; i++)
    {
        cin>>a;
        update(i, a, n);
    }
    for (int i=1; i<=q; i++)
    {
        cin>>cer;
        if (cer==0)
        {
            cin>>a>>b;
            update(a, b, n);
        }
        else if (cer==1)
        {
            cin>>a>>b;
            cout<<0LL+query(b)-query(a-1)<<'\n';
        }
        else
        {
            cin>>a;
            cout<<cautbin(a, n)<<'\n';
        }
    }
}