#include <fstream>
#define D_MAX 100005
#define P(x) ( x&(-x) )
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int a[D_MAX],n,m;
void ADD(int what, int where)
{
    for(int i=where; i<=n; i+=P(i))
    {
        a[i]+=what;
    }
}
int S(int x)
{
    int sum=0;
    for(int i=x; i>0; i-=P(i))
    {
        sum+=a[i];
    }
    return sum;
}
int suma_pe_interval(int p1, int p2)
{
    return S(p2)-S(p1-1);
}
int valoare(int x)
{
    int i=1;
    while(a[i]<x && i<=n)
    {
        if(i+P(i)<=n && a[i+P(i)]<=x)
        {
            i+=P(i);
            if(a[i]==x)
                return i;
        }
        else if((i+P(i)<=n && a[i+P(i)]>x)||i+P(i)>n)
        {
            x-=a[i];
            i++;
            if(a[i]==x)
            {
                return i;
            }
            else if(i>n)
                return -1;
        }
        else if(i+P(i)>n)
            return -1;
    }
    if(a[i]==x)
        return i;
    else
        return -1;
}
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        ADD(x,i);
    }
    for(int i=0; i<m; i++)
    {
        int x,y,z;
        cin >> z;
        if(z==0)
        {
            cin >> x >> y;
            ADD(y,x);
        }
        else if(z==1)
        {
            cin >> x >> y;
            cout << suma_pe_interval(x,y) << '\n';
        }
        else if(z==2)
        {
            cin >> x;
            cout << valoare(x) << '\n';
        }
    }
    return 0;
}