#include <iostream>
#include <fstream>
#include <bitset>

#define nmax 100005
using namespace std;
int n,m;
int aib[nmax];
int tip,a,b;
int lg(int x)
{
    int nrz=0;
    while(!(x&1))
    {
        x >>= 1;
        nrz++;
    }
    return 1 << nrz;
}

void update(int i,int x)
{
    for(int j=i;j<=n;)
    {
        aib[j]+=x;
        j+=lg(j);
    }
}
void read()
{
    scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d ",&x);
        update(i,x);
    }
}

int query(int x)
{
    int sum=0;
    for(int i=x;i>=1;)
    {
        sum+=aib[i];
        i-=lg(i);
    }
    return sum;
}

int search_aib(int st,int dr)
{
    if(st==dr)
        if(query(st)==a)
            return st;
        else return -1;
    int mij=(st+dr)/2;
    int s = query(mij);
    if(a==s)
        return mij;
    if(a<s)
        return search_aib(st,mij);
    return search_aib(mij+1,dr);
}
void solve()
{
    for(int i=1;i<=m;i++)
    {
        scanf("%d ",&tip);
        if(tip==0)
        {
            scanf("%d %d",&a,&b);
            update(a,b);
            continue;
        }
        if(tip==1)
        {
            scanf("%d %d",&a,&b);
            printf("%d\n",query(b)-query(a-1));
            continue;
        }
        if(tip==2)
        {
            scanf("%d ",&a);
            printf("%d\n",search_aib(1,n));
        }
    }
}
int main()
{
    freopen("aib.in","r",stdin);
   freopen("aib.out","w",stdout);
    read();
    solve();
    return 0;
}