#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
#define NMAX 100000
int n,m,aib[NMAX+5],c,a,b;
int st,dr,ok,k;
int ub(int x)
{
    return (x & (-x));
}
void add(int x,int val)
{
    for(int i=x;i<=n;i+=ub(i))
    {
        aib[i]+=val;
    }
}
int sum(int x)
{
    int rez=0;
    for(int i=x;i>=1;i-=ub(i))
    {
        rez+=aib[i];
    }
    return rez;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>c;
        add(i,c);
    }
    while(f>>c)
    {
        if(c==0)
        {
            f>>a>>b;
            add(a,b);
        }
        else if(c==1)
        {
            f>>a>>b;
            g<<sum(b)-sum(a-1)<<endl;
        }
        else if(c==2)
        {
            f>>a;
            st=1;
            dr=n;
            ok=1;
            k=-1;
            while(st<=dr&&ok)
            {
                int mij=(st+dr)/2;
                if(sum(mij)<a)
                {
                    st=mij+1;
                }
                else if(sum(mij)>a)
                {
                    dr=mij-1;
                }
                else if(sum(mij)==a)
                {
                    ok=0;
                    k=mij;
                }
            }
            g<<k<<endl;
        }
    }
    return 0;
}