#include <bits/stdc++.h>
using namespace std;

#define dim 100001
#define zeros(x)((x^(x-1))&x)
 ifstream fin("aib.in");
 ofstream fout("aib.out");

 int n, m, k, v[dim];
int op, x, y;
bool gasit=0;
 void add(int val, int pos)
 {
     for(int i=pos;i<=n;i+=zeros(i))
     {
         v[i]+=val;
     }
 }

 int sum(int x)
 {
     int s=0;
     for(int i=x;i>0;i-=zeros(i))
     {
         s+=v[i];
     }
     return s;
 }
int suma(int st,int dr)
{
    return sum(dr)-sum(st-1);
}

int cautbin(int a)
{
    int st,dr,mid;
    st=1;
    dr=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(a<suma(1,mid))
            dr=mid;
        if(a>suma(1,mid))
            st=mid+1;
        if(a==suma(1,mid))
            return mid;
    }
    if(a==suma(1,st))
    return st;
    else
        return -1;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>k;
        add(k,i);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>op;
        if(op<2)
        {
            fin>>x>>y;
            if(op==0)
                add(y,x);
            else
                fout<<sum(y)-sum(x-1)<<'\n';
        }
        else
        {
            fin>>x;
            fout<<cautbin(x)<<'\n';
        }
    }


    return 0;
}