#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];
int B1[1000010];
int B2[1000010];

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

int Query(int AIB[],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(AIB,b) - Query(AIB,a - 1)<<'\n';
                break;
            case 2:
                f>>a;
                g<<Search(a)<<'\n';
                break;
        }
    }
    g.close();
}

//gasirea unei valori punctuale: Query(x) - Query(x - 1) are O(log n), dar asta are O(1) amortizat
int find(int x)
{
    int s = AIB[x];
    for(int i = x - 1;i != x & (x - 1) && i > 0;i -= zeros(i))
        s -= AIB[i];
    return s;
}

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

void AddRange(int l,int r,int val)
{
    Update(B1, l, val);
    Update(B1, r + 1, - val);
    Update(B2, l,val * (l -1 ));
    Update(B2,r + 1, -val * r);
}

int QueryUpdateRange(int pos)
{
   return Query(B1,pos) * pos - Query(B2,pos);
}

int QueryRange(int a,int b)
{
    return QueryUpdateRange(b) - QueryUpdateRange(a - 1);
}

int main()
{
    Read();
    memset(AIB, 0, sizeof(AIB));
    n = 9;
    AddRange(1,4,5);
    cout<<QueryRange(2,3);
    return 0;
}