#include <iostream>
#include <stdio.h>

using namespace std;
#define nmax 100010

int a[nmax];
int N,M;

void update(int poz, int val)
{
    int K=0;
    while (poz <= N)
    {
        a[poz]=a[poz]+val;
        while ( !(poz & (1<<K)) ) K++;
        poz=poz+(1<<K);
        K++;
    }
}

int query(int poz)
{
    int S,K;
    S=0; K=0;
    while ( poz > 0 )
    {
        S=S+a[poz];
        while ( !( poz&(1<<K)) ) K++;
        poz=poz-(1<<K);
        K++;
    }
    return S;
}

int caut_bin(int left,int right,int val)
{
    int i,p=(left+right)/2;
    if ( left==right ) return left;
    else
    {
        if ( val>=query(left) && val<=query(p) ) caut_bin(left,p,val); else
        if ( val>=query(p+1) && val<=query(right) ) caut_bin(p+1,right,val);else return -1;

    }
}

void afis()
{
    int i;

    for (i=1; i<=N; i++) printf("%i ",a[i]);
    printf("\n");
}

int main()
{
    int i,a,b,x;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%i%i",&N,&M);
    for (i=1; i<=N; ++i) {  scanf("%i",&a); update(i,a);  }
    for (i=1; i<=M; ++i)
    {
        scanf("%i",&x);
        if (x==0)
        {
            scanf("%i%i",&a,&b);
            update(a,b);
        } else
        if (x==1)
        {
            scanf("%i%i",&a,&b);
            printf("%i\n",query(b)-query(a-1));
        } else
        {
            scanf("%i",&a);
            printf("%i\n",caut_bin(1,N,a));
        }
    }
    return 0;
}