#include <fstream>
#include <cstdio>
#define NMAX 100002
#define nr0(x) x&(-x)
using namespace std;
ofstream fout("aib.out");
int aib[NMAX],a,task,b;
int n,m;
void adaug(int a,int poz)
{
    for(int i=poz;i<=n;i+=nr0(i))
        aib[i]+=a;
}
int suma(int poz)
{
    int s=0;
    for(int i=poz;i>=1;i-=nr0(i))
        s=s+aib[i];
    return s;
}
int caut(int a)
{
    int p;
    long long i,s=0;
    for(p=1;p<=n;p=p<<1)
        i++;
    for(i=0;p!=0;p=p>>1)
    {
        if(i+p<=n)
            if(s+aib[i+p]<=a)
            {
                s=s+aib[i+p],i=i+p;
                if(s==a) return i;
            }
    }
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        adaug(a,i);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&task);
        if(task==0)
        {
            scanf("%d%d",&b,&a);
            adaug(a,b);
        }
        else
        if(task==1)
        {
            scanf("%d%d",&a,&b);
            fout<<suma(b)-suma(a-1)<<'\n';
        }
        else
        {
            scanf("%d",&a);
            fout<<caut(a)<<'\n';
        }
    }
}