#include <bits/stdc++.h>
#define z(i) (i & -i)
#define int long long

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int aib[100001],n;

void add(int val,int poz)
{
    for(;poz<=n;poz += z(poz))
        aib[poz]+=val;
}
int q1(int x)
{
    int ans=0;
    for(;x>0;x-= z(x))
        ans+=aib[x];
    return ans;
}
int q2(int x)
{
    int l=1,r=n,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(q1(m)==x)
            return m;
        if(q1(m)<x)
            l=m+1;
        else
            r=m-1;
    }
    return -1;
}

signed main()
{
    int qr,q,i,x,b;
    fin>>n>>q;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        add(x,i);
    }
    for(i=1;i<=q;i++)
    {
        fin>>qr;
        if(qr==0)
        {
            fin>>x>>b;
            add(b,x);
        }
        else if(qr==1)
        {
            fin>>x>>b;
            fout<<q1(b)-q1(x-1)<<'\n';
        }
        else
        {
            fin>>x;
            fout<<q2(x)<<'\n';
        }
    }
    return 0;
}