#include <fstream>
using namespace std;
int aib[100005],n;
ifstream in ("aib.in");
ofstream out ("aib.out");
int suma(int x)
{
    int sum=0,x1=x,putere=1;
    while(x)
    {
        sum+=aib[x];
        x1=x;
        putere=1;
        while(x1%2==0)
        {
            putere<<=1;
            x1/=2;
        }
        x-=putere;
    }
    return sum;
}
void adauga(int x, int valoare)
{
    int putere=1;
    int x1=x;
    while(x<=n)
    {
        aib[x]+=valoare;
        x1=x;
        putere=1;
        while(x1%2==0)
        {
            putere<<=1,x1/=2;
        }
        x+=putere;
    }
}
int main()
{
    int m;
    in>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int a;
        in>>a;
        adauga(i,a);
    }
    for (int j=1;j<=m;j++)
    {
        int a,x,y;in>>a;
        if (a==1)
        {
            in>>x>>y;
            out<<suma(y)-suma(x-1)<<'\n';
        }
        else if (a==0)
        {
            in>>x>>y;
            adauga(x,y);
        }
        else if(a==2)
        {
            in>>x;
            int pas=1,i=1;
            for (pas=1;(long)pas<=n;pas<<=1);
            for (i=0;pas;pas>>=1)
            {
                if(i+pas<=n&&suma(i+pas)<x)
                    i+=pas;
            }
            if(suma(i+1)==x)
                out<<i+1<<'\n';
            else
                out<<-1<<'\n';
        }
    }
}