#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

const int N=100010;

int n,m,v[N];


void add(int a,int b)
{
    for(;a<=n;a+=a&(-a))
        v[a]+=b;
}


int get_sum(int a)
{
    int r=0;
    for(;a>0;a-=a&(-a))
        r+=v[a];
   return r;
}

int b_search(int val)
{
    int lo=0,hi=n,mi;

    while(hi-lo>1)
    {
        mi=(lo+hi)/2;
        if(get_sum(mi)<val)
            lo=mi;
        else
            hi=mi;
    }
    if(get_sum(hi)!=val)
        hi=-1;
    return hi;
}

int main()
{
    int x,a,b;
    f>>n>>m;

    for(int i=1;i<=n;i++)
    {
        f>>x;
        add(i,x);
    }

    for(;m;m--)
    {
        f>>x>>a;
        if(x==2){g<<b_search(a)<<'\n';continue;}
        f>>b;
        if(x==0){add(a,b);continue;}
        if(x==1)g<<get_sum(b)-get_sum(a-1)<<'\n';
    }

    return 0;


}