#include <bits/stdc++.h>

using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

const int dim = 1e5 + 5;

int binInd_tree[dim] , n , q;

void Update (int position , int value)
{
    int c = 0;
    while(position <= n)
        {
            binInd_tree[position] += value;
            while((position & (1 << c)) == 0)
                ++c;
            position += (1 << c);
            ++c;
        }
}

int Query1 (int position)
{
    int c = 0 , summ = 0;
    while(position > 0)
        {
            summ += binInd_tree[position];
            while((position & (1 << c)) == 0) ++c;
            position -= (1 << c);
            ++c;
        }
    return summ;
}

int Query2 (int summ)
{
    int left = 1 , right = n;
    while(left <= right)
        {
            int middle = (left + right) / 2;
            int sum = Query1(middle);
            if(sum == summ)
                return middle;
            else if(sum < summ)
                left = middle + 1;
            else
                right = middle - 1;
        }
    return -1;
}

int main()
{
    fin >> n >> q;
    for(int i = 1 ; i <= n ; ++i)
        {
            int x;
            fin >> x;
            Update(i , x);
        }
    while(q--)
        {
            int op;
            fin >> op;
            if(op == 0)
                {
                    int p , v;
                    fin >> p >> v;
                    Update(p , v);
                }
            else if(op == 1)
                {
                    int l , r;
                    fin >> l >> r;
                    fout << Query1(r) - Query1(l - 1) << '\n';
                }
            else
                {
                    int s;
                    fin >> s;
                    fout << Query2(s) << '\n';
                }
        }
}