#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 main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>k;
        add(k,i);
    }
    for(int i=1;i<=n;i++)
    {
        fout<<v[i]<<" ";
    }
    fout<<'\n';
    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
        {
            gasit=0;
            fin>>x;
            int st=1, dr=n, mij, actualSum=0;;
            while(st<=dr && !gasit)
            {
                mij=(st+dr)/2;
                actualSum=sum(mij);
                if(actualSum==x)
                {
                    gasit=1;
                    fout<<mij<<'\n';
                }
                else if(actualSum<x)
                    st=mij+1;
                else
                    dr=mij;
            }
            if(!gasit)
                fout<<"-1"<<'\n';
        }
    }


    return 0;
}