#include <cstdio>
#define formulaCiudata(x) (-x)&x

using namespace std;

int n, m;
int aib[100005], test;

void update(int indx, int value)
{
    for(int i = indx; i <= n; i += formulaCiudata(i))
        aib[i] += value;
}

int suma(int indx)
{
//    int s=0;
//    for(int i=indx; i>0; i-=formulaCiudata(i))
//        s+=aib[i];
//    return s;

    if(indx == 0)
        return 0;
    return aib[indx] + suma(indx - formulaCiudata(indx));
}

int bin(int value)
{
    int st = 1, dr = n, mij, poz = -1;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(suma(mij) == value)
        {
            poz = mij;
            dr = mij - 1;
        }
        else if(suma(mij) > value)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return poz;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d ", &x);
        update(i, x);
    }

    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &test);
        if(test == 0)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            update(x, y);
        }
        else
            if(test == 1)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", suma(y) - suma(x - 1));
        }
        else
        {
            int x;
            scanf("%d", &x);
            printf("%d\n", bin(x));
        }
    }
    return 0;
}