#include <bits/stdc++.h>

using namespace std;
#define zeros(x) ((x ^ (x - 1)) & x)
ifstream f("aib.in");
ofstream g("aib.out");
int n,m;
int AIB[1000010];

void Add(int x,int val)
{
    for(int i = x;i <= n;i += zeros(i))
        AIB[i] += val;
}

int Query(int x)
{
    int res = 0;
    for(int i = x;i >= 1;i -= zeros(i))
        res += AIB[i];
    return res;
}

int Search(int val)
{
    int rep,i;
    for(rep = 1;rep < n;rep <<= 1);
    for(i = 0;rep;rep >>= 1)
        if(i + rep <= n && AIB[i + rep] <= val)
        {
            i += rep;
            val -= AIB[i];
            if(!val) return i;
        }
    return -1;
}

void Read()
{
    int a,b,k;
    f>>n>>m;
    for(int i = 1;i <= n;++i)
    {
        f>>a;
        Add(i , a);
    }
    for(int i = 1;i <= m;++i)
    {
        f>>k;
        switch(k)
        {
            case 0:
                f>>a>>b;
                Add(a , b);
                break;
            case 1:
                f>>a>>b;
                g<<Query(b) - Query(a - 1)<<'\n';
                break;
            case 2:
                f>>a;
                g<<Search(a)<<'\n';
                break;
        }
    }
    g.close();
}

int main()
{
    Read();
    return 0;
}