#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int aib[100001];
int n,m;
void introduce(int v,int poz)
{
    while(poz<=n)
    {
        aib[poz]+=v;
        poz=poz+(poz&(-poz));
    }
}
int f(int poz)
{
    int rez=0;
    while(poz>0)
    {
        rez+=aib[poz];
        poz=poz-(poz&(-poz));
    }
    return rez;
}
int suma(int st,int dr)
{
    return f(dr)-f(st-1);
}

int cautbin(int a)
{
    int st,dr,mid;
    st=1;
    dr=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(a<suma(1,mid))
            dr=mid;
        if(a>suma(1,mid))
            st=mid+1;
        if(a==suma(1,mid))
            return mid;
    }
    if(a==suma(1,st))
    return st;
    else
        return -1;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        fin>>a;
        introduce(a,i);
    }
    for(int i=1;i<=m;i++)
    {
        int t;
        fin>>t;
        if(t==0)
        {
            int a,b;
            fin>>a>>b;
            introduce(b,a);
        }
        if(t==1)
        {
            int a,b;
            fin>>a>>b;
            fout<<suma(a,b)<<"\n";
        }
        if(t==2)
        {
            int a;
            fin>>a;
            fout<<cautbin(a)<<"\n";
        }
    }
    return 0;
}