#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
int n;
int AIB[Nmax];
inline void update(const int &x, const int &y)
{
    int poz=x,nr=0;
    while(poz<=n)
    {
        AIB[poz]+=y;
        while(!(poz&(1<<nr)))
            nr++;
        poz+=(1<<nr);
        nr++;
    }
}
inline int querry(const int &x)
{
    int poz=x,nr=0,sol=0;
    while(poz)
    {
        sol+=AIB[poz];
        while(!(poz&(1<<nr)))
            nr++;
        poz-=(1<<nr);
        nr++;
    }
    return sol;
}
inline int CB(const int &x)
{
    int p=1,q=n,rez,m;
    while(p<=q)
    {
        m=(p+q)/2;
        rez=querry(m);
        if(rez==x) return m;
        else
        {
            if(rez<x) p=m+1;
            else q=m-1;
        }
    }
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int i,k,m,op,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&k);
        update(i,k);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==0)
        {
            scanf("%d%d",&x,&y);
            update(x,y);
        }
        else
        {
            if(op==1)
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",querry(y)-querry(x-1));
            }
            else
            {
                scanf("%d",&k);
                printf("%d\n",CB(k));
            }
        }
    }

    return 0;
}