#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;

const int MAXN = 100000;

int aib[MAXN+1], N, M;

int zeros(int x)
{
    return ( x & ( x - 1 ) )^x;
}

void adauga(int index, int value)
{
    for(int i = index; i <= N; i+=zeros(i))
        aib[ i ] += value;
}

int getSum(int x)
{
    int sum = 0;

    for(int i = x; i >= 1; i-=zeros(i))
        sum += aib[ i ];

    return sum;
}

int querrySum(int a, int b)
{
    return getSum( b ) - getSum( a - 1 );
}

void build()
{
    for(int i = 1; i <= N; i++)
    {
        int x;
        scanf("%d",&x);
        adauga(i,x);
    }
}

int querry2(int a)
{
    int left = 1, right = N, k = N + 1;

    while( left <= right )
    {
        int m = ( left + right ) / 2, s = getSum( m );

        if( a == s )
        {
            k = min( k, m );
            right = m - 1;
        }
        else
        {
            if( a < s )
                right = m - 1;
            else
                left = m + 1;
        }
    }

    if( k == N + 1 )
        return -1;

    return k;
}



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

    scanf("%d %d",&N,&M);

    build();

    int cod, a, b;

    for(int i = 1; i <= M; i++)
    {
        scanf("%d",&cod);

        if( cod == 0 )
        {
            scanf("%d %d",&a,&b);
            adauga( a, b );
        }
        else
        if( cod == 1 )
        {
            scanf("%d %d",&a,&b);
            cout<<querrySum( a, b )<<endl;
        }
        else
        {
            scanf("%d",&a);
            cout<<querry2( a )<<endl;
        }
    }

    return 0;
}