#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,bl;
int ad[3010],vl[100010];
int b[1010][3010];
int s[3010],sz;
inline void out(int n)
{
    if(n<0)
    {
        putchar('-');
        n=-n;
    }
    if(n>=10)
    {
        out(n/10);
    }
    putchar(n%10+'0');
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int op,l,r,v;
int il,ir;
int cheak(int x)
{
    int ret=lower_bound(s+1,s+sz+1,x)-s-1;
    for(int i=il;i<=ir;i++)
    {
        if(b[i][1]>=x-ad[i])
        {
            continue;
        }
        if(b[i][bl]<x-ad[i])
        {
            ret+=bl;
            continue;
        }
        ret+=lower_bound(b[i]+1,b[i]+bl+1,x-ad[i])-b[i]-1;
    }
    return ret;
}
void query()
{
    int ml=-(1<<30),mr=(1<<30),mid;
    il=l/bl+1;
    ir=r/bl-1;
    sz=0;
    if(l/bl==r/bl)
    {
        for(int i=l;i<=r;i++)
        {
            s[++sz]=vl[i]+ad[i/bl];
            ml=max(ml,vl[i]+ad[i/bl]);
            mr=min(mr,vl[i]+ad[i/bl]);
        }
    }
    else
    {
        for(int i=l;i<l/bl*bl+bl;i++)
        {
            s[++sz]=vl[i]+ad[i/bl];
            ml=max(ml,vl[i]+ad[i/bl]);
            mr=min(mr,vl[i]+ad[i/bl]);
        }
        for(int i=r/bl*bl;i<=r;i++)
        {
            s[++sz]=vl[i]+ad[i/bl];
            ml=max(ml,vl[i]+ad[i/bl]);
            mr=min(mr,vl[i]+ad[i/bl]);
        }
    }
    sort(s+1,s+sz+1);
    for(int i=il;i<=ir;i++)
    {
        ml=max(ml,b[i][1]+ad[i]);
        mr=min(mr,b[i][bl]+ad[i]);
    }
    while(ml<mr)
    {
        mid=(ml+mr>>1);
        if(cheak(mid)>v)
        {
            mr=mid-1;
        }
        else
        {
            ml=mid;
        }
    }
    out(ml);
}
void maintain(int x)
{
    for(int i=x*bl;i<x*bl+bl;i++)
    {
        b[x][i%bl+1]=vl[i];
    }
    sort(b[x]+1,b[x]+bl+1);
}
void add()
{
    if(l/bl==r/bl)
    {
        for(int i=l;i<=r;i++)
        {
            vl[i]+=v;
        }
        maintain(l/bl);
    }
    else
    {
        for(int i=l;i<l/bl*bl+bl;i++)
        {
            vl[i]+=v;
        }
        maintain(l/bl);
        for(int i=r/bl*bl;i<=r;i++)
        {
            vl[i]+=v;
        }
        maintain(r/bl);
        for(int i=l/bl+1;i<r/bl;i++)
        {
            ad[i]+=v;
        }
    }
}
int main()
{
    n=read();
    m=read();
    bl=17*sqrt(n);
    for(int i=1;i<=n;i++)
    {
        vl[i]=read();
        b[i/bl][i%bl+1]=vl[i];
    }
    while(m--)
    {
        op=read();
        l=read();
        r=read();
        v=read();
        if(op==1)
        {
            if(r-l+1<v)
            {
                out(-1);
                continue;
            }
            query();
        }
        if(op==2)
        {
            add();
        }
    }
    return 0;
}

zk卡时间卡成了0分，宝贝们快来帮帮zk~