#include <iostream>
#include <fstream>
#include <stdio.h>
#define nmax 100001

using namespace std;
long sum[nmax];
long a,b,n,m, sol ;

void update(int poz , int val)
{
    while (poz <= n)
    {
        int p = 0;
        while (!(poz & (1 << p)) ) {p++;}
        sum[poz] += val;
        poz += (1<<p);
    }
}

long query(int num)
{
    int s = 0;
        while (num > 0)
        {
           int p = 0;
        while (!(num & (1 << p)) ) {p++;}
            s += sum[num];
            num -= (1 << p);
        }
    return s;
}

int search(int low,int high , int val)
{
    if (low == high)
    {
        if (query(low) == val) return low;
                else return -1;
    }
    int mid;
    mid = (low + high) / 2;
        int c = query(mid);
            if (c == val) return mid;
            if (c > val) return search(1,mid-1,val);
                    return search(mid+1,high,val);
}

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

    for (int i =1;i<=m;i++)
    {
        int x;
         fscanf(stdin,"%d",&x);
        if (x == 0) { int poz;  fscanf(stdin,"%d%d",&poz,&a); update(poz,a); }
            else if (x == 1)
                { fscanf(stdin,"%i%i",&a,&b);
                    sol = query(b) - query(a-1);
                    printf("%d\n",sol);
                }
                else
                {
                    int k; fscanf(stdin,"%d",&k);
                    printf("%d\n",search(1,n,k));
                }

    }
    return 0;
}