#include <bits/stdc++.h>
using namespace std;
int w;int zf;char c;
int read()
{
	w=0;zf=1;c=getchar();
	while(c<'0'||c>'9'){if(c=='-')zf=-1;c=getchar();}
	while(c>='0'&&c<='9'){w=(w<<3)+(w<<1)+(c^48);c=getchar();}
	return w*zf;
}
int n,q,a[100005],b[100005],d[1005],belong[100005],tag[100005],l[1005],r[1005],kuai,s,ans,sum,len,lll,rrr;
long long mid;
void update(int x,int y,int k)
{
	if(belong[x]==belong[y])
	{
		for(int i=x;i<=y;i++){a[i]+=k;b[i]=a[i];}
		sort(b+l[belong[x]],b+r[belong[x]]+1);
	}
else{
		for(int i=x;i<=r[belong[x]];i++)a[i]+=k;
		for(int i=l[belong[x]];i<=r[belong[x]];i++)b[i]=a[i];
		sort(b+l[belong[x]],b+r[belong[x]]+1);
		for(int i=l[belong[y]];i<=y;i++)a[i]+=k;
		for(int i=l[belong[y]];i<=r[belong[y]];i++)b[i]=a[i];
		sort(b+l[belong[y]],b+r[belong[y]]+1);
		for(int i=belong[x]+1;i<=belong[y]-1;i++)tag[i]+=k;
	}
}
int query(int x,int y,int k)
{
	sum=0;
	for(int i=x;i<=r[belong[x]];i++)if(tag[belong[x]]+a[i]<=k)sum++;
	for(int i=l[belong[y]];i<=y;i++)if(tag[belong[y]]+a[i]<=k)sum++;
	for(int i=belong[x]+1;i<=belong[y]-1;i++)
	{
		int xx=upper_bound(b+l[i],b+r[i]+1,k-tag[i])-b;
		sum+=xx-l[i];
	}
	return sum;
}
int type,ll,rr,k;
int main()
{
	n=read();q=read();kuai=sqrt(n);s=n/kuai;
	for(int i=1;i<=s;i++){l[i]=(i-1)*kuai+1;r[i]=i*kuai;}
	if(r[s]<n){++s;l[s]=r[s-1]+1;r[s]=n;}
	for(int i=1;i<=n;i++)belong[i]=(i-1)/kuai+1;
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	for(int i=1;i<=s;i++)sort(b+l[i],b+r[i]+1);
	while(q--)
	{
		type=read();ll=read();rr=read();k=read();
		if(type==1)
		{
			if(belong[ll]==belong[rr])
			{
				len=0;
				for(int i=ll;i<=rr;i++)d[++len]=a[i];
				nth_element(d+1,d+k,d+len);
				printf("%d\n",d[k]);
			}
		else{
				ans=-1;
				lll=-2e9;rrr=2e9;
				while(lll<=rrr)
				{
					mid=(lll+rrr)>>1;
					if(query(ll,rr,mid)<k)lll=mid+1;
				else{ans=mid;rrr=mid-1;}
				}
				printf("%d\n",ans);
			}
		}
		if(type==2)update(ll,rr,k);
	}
}