#include <bits/stdc++.h>

using namespace std;
int n,aib[100005],x,tip,a,b,m;
ifstream fin("aib.in");
ofstream fout("aib.out");
int lsb(int n)
{
    return (n&(-n));
}
void update(int pos,int val)
{
    while (pos<=n)
    {
        aib[pos]+=val;
        pos+=lsb(pos);
    }
}
int query(int pos)
{
    int rez=0;
    while (pos>0)
    {
        rez+=aib[pos];
        pos-=lsb(pos);
    }
    return rez;
}
int cautare_binara(int n, int x)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (x<=query(mij))
            dr=mij-1;
        else
            st=mij+1;
    }
    if (query(st)==x) return st;
    return -1;
}
int main()
{
    fin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
    for (int i=1;i<=m;i++)
    {
        fin>>tip;
        if (tip!=2)
            fin>>a>>b;
        else
            fin>>a;
        if (tip==0)
            update(a,b);
        if (tip==1)
            fout<<query(b)-query(a-1)<<"\n";
        if (tip==2)
            fout<<cautare_binara(n,a)<<"\n";
    }
}