#include <fstream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
#define zeros(x) ( (x ^ (x - 1)) & x )
int n,m,x,i,v[100001],a,b,c;
void add(int poz,int val)
{
    for(int i=poz; i<=n; i+=zeros(i))
        v[i]+=val;
}
int compute(int poz)
{
    int s=0;
    for(int i=poz; i>=1; i-=zeros(i))
        s+=v[i];
    return s;
}
int cauta(int val)
{
    int i=1, j=n, m, x;
    while(i<=j)
    {
        m=(i+j)>>1;
        x=compute(m);
        if(x==val)
            return m;
        else if(x>val) j=m-1;
             else i=m+1;
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        cin>>x;
        add(i,x);
    }
    for(i=1; i<=m; i++)
    {
       cin>>a>>b; if(a!=2) cin>>c;
       if(a==0)
           add(b,c);
       if(a==1)
            cout<<compute(c)-compute(b-1)<<"\n";
       if(a==2)
           cout<<cauta(b)<<"\n";
    }
}