#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int DIM = 100005;
const int BITMASK = 31;

int pos,n,m,event,AIB[DIM],x,a,b,q;

int GetPos(int x)
{
    for(int bit=BITMASK;bit>=0;bit--)
    {
        if(x&(1<<bit))
            return bit;
    }
    return 0;
}

int GetSum(int x)
{
    pos=GetPos(x);
    int ans=0;
    for(int bit=0;bit<=pos;bit++)
    {
        if(x&(1<<bit))
        {
            ans+=AIB[x];
            x=x&(~(1<<bit));
            if(!x)
                break;
        }
    }
    return ans;
}

void PosSum(int x, int value)
{
    do
    {
        AIB[x]+=value;
        x+=x&-x;
    }while(x<=DIM);
}

int Search(int value)
{
    int st=1,dr=DIM,sol=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(GetSum(mij)==value)
        {
            sol=mij;
            break;
        }
        if(GetSum(mij)>value)
            dr=mij-1;
        if(GetSum(mij)<value)
            st=mij+1;
    }
    if(sol>0)
    {
        int j=sol;
        while(j>0 && GetSum(j)==value)
        {
            sol=j;
            j--;
        }
    }
    return sol;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        PosSum(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>event;
        switch(event)
        {
        case 0:
            {
                fin>>a>>b;
                PosSum(a,b);
                break;
            }
        case 1:
            {
                fin>>a>>b;
                q=GetSum(b)-GetSum(a-1);
                fout<<q<<'\n';
                break;
            }
        default:
            {
                fin>>a;
                fout<<Search(a)<<'\n';
                break;
            }
        }
    }
}