#include <iostream>
#include <fstream>

#define nmax 100001

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

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()
{
        f >> n >> m;
        for (int i=1;i<=n;i++)
        {
            int x;
            f >> x;
            update(i,x);
        }

    for (int i =1;i<=m;i++)
    {
        int x;
        f >> x;
        if (x == 0) { int poz; f >> poz >> a; update(poz,a); }
            else if (x == 1) { f >> a >> b; sol = query(b) - query(a-1); g << sol << '\n'; }
                else
                {
                    int k; f >> k;
                      g << search(1,n,k) << '\n';
                }

    }
    return 0;
}