#include <cstdio>
#define p2(a) (((a^(a-1))+1)>>1)
#define dmax 100003
using namespace std;

int aib[dmax], n, m, k;

void update(int, int);
int sum(int, int);
void read();

void read()
{

    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    scanf("%i %i", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%i", &k), update(i, k);
}

void update(int a, int b)
{

    while(a<=n)
    {
        aib[a]+=b;
        int x=p2(a);
        a=a+p2(a);
    }
}

int sum(int a)
{
    int sum=0;
    for(; a>0; a-=p2(a))
        sum+=aib[a];
    return sum;
}

int sumk(int a)
{

    int mid=n/2, i2=(mid+1)/2, i3=mid, i4=mid, i5=mid;
    while(0< mid && mid<=n && i5!=1)
    {
        if(sum(mid)==a)
            return mid;
        else if(sum(mid)>a)
            mid-=i2;
        else if(sum(mid)<a)
            mid+=i2;

        i5=i4;
        i4=i3;
        i3=i2;
        i2=(i2+1)/2;

    }
    return -1;
}

void solve()
{
    int a, b;
    for(int i=1; i<=m; ++i)
    {
        scanf("%i", &a);
        if(a==0)
        {
            scanf("%i%i", &a, &b);
            update(a, b);
        }
        else if(a==1)
        {
            scanf("%i%i", &a, &b);
            printf("%i\n", sum(b)-sum(a-1));
        }
        else if(a==2)
        {
            scanf("%i", &b);
            printf("%i\n", sumk(b));
        }
    }

}
int main()
{
    read();
    solve();
    return 0;
}