#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n,m,A[N];
int suma(int p)
{
    int ret=0;
    for(;p;p-=p&(-p))
        ret+=A[p];
    return ret;
}
void aduna(int p,int val)
{
    for(;p<=n;p+=p&(-p))
        A[p]+=val;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        aduna(i,x);
    }
    for(;m;m--)
    {
        int t;
        f>>t;
        if(t==0)
        {
            int a,b;
            f>>a>>b;
            aduna(a,b);
        }
        else if(t==1)
        {
            int a,b;
            f>>a>>b;
            g<<suma(b)-suma(a-1)<<'\n';
        }
        else
        {
            int a;
            f>>a;
            int st=0,dr=n;
            while(dr-st>1)
            {
                int mi=(st+dr)/2;
                if(suma(mi)<a)
                    st=mi;
                else
                    dr=mi;
            }
            if(suma(dr)!=a)
                dr=-1;
            g<<dr<<'\n';
        }
    }
    return 0;
}



//
//
//
//
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
//  *   *   *   *   *     *     *     *     *     *     *   2k+1 = ....1
//  * *     * *     *  *        *  *        *  *            4k+2 = ...10
//  * * * *         *  *  *  *              *  *  *  *      8k+4 = ..100
//  * * * * * * * *                                        16k+8 = .1000
//  * * * * * * * * *  *  *  *  *  *  *  *
//
//s[1,19] = A[19]+A[18]+A[16](19=16+2+1=10011)
//19 10011 (19 = 2k+1 ->18) scad 1 adica ultimul bit nenul
//18 10010 (18 = 4k+2 ->16) scad 2 adica ultimul bit nenul
//16 10000 (16 = 32k+16->0) scad 16 adica ultimul bit nenul
// 0 00000
//
// ultimul bit nenul
// LSB(x) = x&(-x)
//s[1,14] = A[14]+A[12]+A[ 8]
//
//La v[11] adun y
//-> la A[11] adun y
//-> la A[12] adun y
//-> la A[16] adun y
//
//11  1011 (+1)
//12  1100  (4=100)
//16 10000   (16=10000)
//32>12 (32>N)