#include<bits/stdc++.h>
using namespace std;
int n,m,nm,b[100005],c[320],d[320],e[320],k,x,y,z,atp,btp,xx,yy,zz,l,mid,r,ans;
struct node
{
	int id,n;
} a[100005],aa[320],bb[320],o[320];
bool operator<(node x,node y)
{
	return x.n<y.n;
}
int read()
{
	int result=0,k=1;
	char ch=getchar();
	while (ch<'0' || ch>'9')
	{
		if (ch=='-')
		k=-1;
		ch=getchar();
	}
	while ('0'<=ch && ch<='9')
	{
		result=result*10+(ch^48);
		ch=getchar();
	}
	return k*result;
}
int doit(int l,int r,int x)
{
	int result=upper_bound(o+1,o+zz+1,(node){0,x})-o-1;
	for (int i=b[l]+1;i<b[r];++i)
	result+=upper_bound(a+c[i],a+d[i]+1,(node){0,x-e[i]})-a-c[i];
	return result;
}
int main()
{
	n=read();
	m=read();
	nm=round(sqrt(n*30));
	for (int i=1;i<=n;++i)
	{
		a[i].id=i;
		a[i].n=read();
		b[i]=(i-1)/nm+1;
		if (c[b[i]]==0)
		c[b[i]]=i;
		d[b[i]]=i;
	}
	for (int i=1;i<=b[n];++i)
	sort(a+c[i],a+d[i]+1);
	while (m--)
	{
		k=read();
		x=read();
		y=read();
		z=read();
		if (k==1)
		{
			if (1<=z && z<=y-x+1)
			{
				atp=0;
				btp=0;
				xx=1;
				yy=1;
				zz=0;
				for (int i=c[b[x]];i<=d[b[x]];++i)
				if (x<=a[i].id && a[i].id<=y)
				{
					aa[++atp]=a[i];
					aa[atp].n+=e[b[x]];
				}
				if (b[x]<b[y])
				for (int i=c[b[y]];i<=d[b[y]];++i)
				if (x<=a[i].id && a[i].id<=y)
				{
					bb[++btp]=a[i];
					bb[btp].n+=e[b[y]];
				}
				while (xx<=atp && yy<=btp)
				if (aa[xx]<bb[yy])
				o[++zz]=aa[xx++];
				else
				o[++zz]=bb[yy++];
				while (xx<=atp)
				o[++zz]=aa[xx++];
				while (yy<=btp)
				o[++zz]=bb[yy++];
				l=o[1].n;
				r=o[zz].n;
				for (int i=b[x]+1;i<b[y];++i)
				{
					l=min(l,a[c[i]].n+e[b[i]]);
					r=max(r,a[d[i]].n+e[b[i]]);
				}
				ans=r;
				--r;
				while (l<=r)
				{
					mid=l+r>>1;
					if (doit(x,y,mid)>=z)
					{
						ans=mid;
						r=mid-1;
					}
					else
					l=mid+1;
				}
				cout<<ans<<'\n';
			}
			else
			cout<<"-1\n";
		}
		else
		{
			atp=0;
			btp=0;
			xx=1;
			yy=1;
			zz=c[b[x]];
			for (int i=c[b[x]];i<=d[b[x]];++i)
			if (x<=a[i].id && a[i].id<=y)
			{
				a[i].n+=z;
				aa[++atp]=a[i];
			}
			else
			bb[++btp]=a[i];
			while (xx<=atp && yy<=btp)
			if (aa[xx]<bb[yy])
			a[zz++]=aa[xx++];
			else
			a[zz++]=bb[yy++];
			while (xx<=atp)
			a[zz++]=aa[xx++];
			while (yy<=btp)
			a[zz++]=bb[yy++];
			if (b[x]<b[y])
			{
				atp=0;
				btp=0;
				xx=1;
				yy=1;
				zz=c[b[y]];
				for (int i=c[b[y]];i<=d[b[y]];++i)
				if (x<=a[i].id && a[i].id<=y)
				{
					a[i].n+=z;
					aa[++atp]=a[i];
				}
				else
				bb[++btp]=a[i];
				while (xx<=atp && yy<=btp)
				if (aa[xx]<bb[yy])
				a[zz++]=aa[xx++];
				else
				a[zz++]=bb[yy++];
				while (xx<=atp)
				a[zz++]=aa[xx++];
				while (yy<=btp)
				a[zz++]=bb[yy++];
				for (int i=b[x]+1;i<b[y];++i)
				e[i]+=z;
			}
		}
	}
}