#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n,m;
vector<long long> aib;
vector<int> forBin;
long long int findSum(int stop)
{
    long long int sum=0;
    while(stop>0)
    {
        sum+=aib[stop];
        stop-=stop&-stop;
    }
    return sum;
}
long long int calculateSum(int start,int stop)
{
    if(start==1)
        return findSum(stop);
    return findSum(stop)-findSum(start-1);
}
bool comp(int a,int b)
{
    return findSum(a)>findSum(b);
}

int binary(int a)
{
    int idx1=0,idx2=n+1,mid;
    while(idx2-idx1>1)
    {
        mid=(idx1+idx2)/2;
        if(a<=findSum(mid))
        {
            idx2=mid;
        }
        else
            idx1=mid;
    }
    return idx2;
}
int main()
{

    fin>>n>>m;
    aib.resize(n+1);
    forBin.resize(n+1);
    for(int i=1;i<=n;i++)
        forBin[i]=i;
    for(int i=1;i<=n;i++)
    {
        int j=i,nr;
        fin>>nr;
        while(j<=n)
        {
            aib[j]+=nr;
            j+=j & -j;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        cout<<aib[i]<<" ";
    }
    cout<<"\n";*/
    int type,a,b;
    for(int i=1;i<=m;i++)
    {
        fin>>type;
        if(type==0)
        {
            fin>>a>>b;
            while(a<=n)
            {
                aib[a]+=b;
                a+=a & -a;
            }
            /*for(int i=1;i<=n;i++)
            {
                cout<<aib[i]<<" ";
            }
            cout<<"\n";*/
        }
        else if(type==1)
        {
            fin>>a>>b;
            int ans=calculateSum(a,b);
            fout<<ans<<"\n";
            cout<<ans<<"\n";
        }
        else if(type==2)
        {
            fin>>a;
            /*for(int i=1;i<=n;i++)
            {
                cout<<aib[i]<<" ";
            }
            cout<<"\n";*/
            int place=binary(a);
            if(place==n+1 || findSum(place)!=a)
            {
                fout<<-1<<"\n";
                cout<<-1<<"\n";
            }
            else if(findSum(place)==a)
            {
                fout<<place<<"\n";
                cout<<place<<"\n";
            }
        }

    }
}