#include <iostream>
#include <fstream>
#define zero(x) ((x ^ (x - 1)) & x)
using namespace std;

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

const int NMax = 100005;
int n, q, query, aib[NMax];

void Update( int poz, int val)
{
    while(poz <= n)
    {
        aib[poz] += val;
        poz += zero(poz);
    }
}

int Query(int poz)
{
    int sum = 0;
    while(poz)
    {
        sum += aib[poz];
        poz -= zero(poz);
    }
    return sum;
}

int Binary_Search( int val)
{
    int st = 1, dr = n + 1, poz = n + 1, m, S;
    S = Query(n);
    if(S == val) return n;
    while(st <= dr)
    {
        m = (st + dr) >> 1;
        S = Query(m);
        if(val < S)
        {
            dr = m - 1;
        }
        else if(val == S)
        {
            poz = min(poz, m);
            dr = m - 1;
        }
        else if(val > S)
        {
            st = m + 1;
        }
    }
    if(poz == n + 1) return -1;
    return poz;
}

int main()
{
    int x, poz, val,a ,b;
    f >> n >> q;
    for(int i = 1; i <= n; ++i)
    {
        f >> x;
        Update(i, x);
    }
    for(int i = 1; i <= q; ++i)
    {
        f >> query;
        if(!query)
        {
            f >> poz >> val;
            Update(poz, val);
        }
        else if(query == 1)
        {
            f >> a >> b;
            g << Query( b ) - Query( a - 1 ) << '\n';
        }
        else
        {
            f >> a;
            g << Binary_Search( a ) << '\n';
        }
    }
}