#include <iostream>
#include <fstream>
#define NMAX 100010
using namespace std;

int n,m,v[NMAX];

int cauta (int val)
{
    int step,i;

    for(step=1;step<n;step<<=1);

    for(int i=0;step;step>>=1)
    {
        if(i+step<=n && val>=v[step+i])
        {
            i+=step;val-=v[i];
            if(!val) return i;
        }
    }
    return -1;
}
int search(int poz)
{
    int C=0,s=0;
    while(poz>0)
    {
        s+=v[poz];
        while(!(poz & (1<<C))) C++;
        poz-=(1<<C);
        C+=1;
    }
    return s;
}
void insert(int poz,int val)
{
    int C=0;
    while(poz<=n)
    {
        v[poz]+=val;
        while(!(poz & (1<<C))) C++;
        poz+=(1<<C);
        C+=1;
    }
}
int main()
{
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>m;
    int tip,x,y;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        insert(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>tip;
        if(tip==0)
        {
            fin>>x>>y;
            insert(x,y);
        }
        else if(tip==1)
        {
            fin>>x>>y;
            fout<<search(max(x,y))-search(min(x,y)-1)<<"\n";
        }
        else
        {
            fin>>x;
            fout<<cauta(x)<<"\n";
        }
    }
    return 0;
}