#include <bits/stdc++.h>

using namespace std;

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

int n,q;
int v[100001];
int tree[100001];
int siz=0;

int aflareSize(int a)
{
    return (1<<(32-__builtin_clz(a-1)));
}

void calculare()
{
    for(int i=1;i<=siz;i++)
    {
        int sum=0;
        for(int j=0;j<(i&-i);j++)
            sum+=v[i-j];
        tree[i]=sum;
    }
}

int query(int k)
{
    int sum=0;
    while(k>0)
    {
        sum+=tree[k];
        k-=(k&-k);
    }
    return sum;
}

void update(int a,int b)
{
    v[a]+=b;
    while(a<=siz)
    {
        tree[a]+=b;
        a+=a&-a;
    }
}

int query2(int k)
{
    int st=0,dr=2*siz;
    while(dr-st>2)
    {
        int mi=(st+dr)/2;
        if(tree[mi]>k)
            dr=mi;
        else if(tree[mi]<=k)
        {
            k-=tree[mi];
            if(k==0)
                return mi;
            st=mi;
        }
    }
    int mi=(st+dr)/2;
    if(k==tree[mi])
        return mi;
    return -1;
}
void afisare()
{
    for(int i=1;i<=siz;i++)
        cout<<tree[i]<<" ";
    cout<<'\n';
}

int main()
{
    fin>>n>>q;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    siz=aflareSize(n);
    calculare();
   // afisare();
    for(int i=0;i<q;i++)
    {
        int op,a,b;
        fin>>op;
        switch (op)
        {
            case 0:
                fin>>a>>b;
                update(a,b);
                break;
            case 1:
                fin>>a>>b;
                fout<<query(b)-query(a-1)<<'\n';
                break;
            case 2:
                fin>>a;
                fout<<query2(a)<<'\n';
                break;
        }
    }
   // afisare();
    return 0;
}