#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n, m, AIB[N];
void aduna(int poz,int val)
{
    /// la pozitia poz se aduna valoarea val
    for( ; poz <= n; poz += poz&(-poz))
        AIB[poz] += val;
}
int suma(int poz)
{
    int s=0;
    for( ; poz ; poz -= poz&(-poz))
        s += AIB[poz];
    return s;
}
int suma(int st,int dr)
{
    return suma(dr) - suma(st-1);
}
int main()
{
    f >> n >> m;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        aduna(i,x);
    }
    for( ;m ; m--)
    {
        int op,x,y;
        f>>op>>x;
        if(op==0)
        {
            f>>y;
            aduna(x,y);
        }
        else
            if(op==1)
        {
            f>>y;
            g<<suma(x,y)<<'\n';
        }
        else
        {
            /// cautare binara
            /// pe st voi avea mereu valoare strict mai mica decat vreau eu
            /// pe dr voi avea mereu valoare mai mare sau egala decat vreau eu
            int st=0,dr=n,mi;
            while(dr-st>1)
            {
                mi=(st+dr)/2;
                if(suma(mi)<x)
                    st=mi;
                else
                    dr=mi;
            }
            if(suma(dr)!=x)
                dr=-1;
            g<<dr<<'\n';
        }
    }
    return 0;
}