24pts

#include<bits/stdc++.h>
using namespace std;
int n,m,nm,b[100005],c[320],d[320],e[320],k,x,y,z,l,mid,r,ans;
struct node
{
	int id,n;
} a[100005];
bool operator<(node x,node y)
{
	return x.n<y.n;
}
int doit(int l,int r,int x)
{
	int result=0;
	for (int i=c[b[l]];i<=d[b[l]];++i)
	if (l<=a[i].id && a[i].id<=r && a[i].n+e[b[i]]<=x)
	++result;
	if (b[l]<b[r])
	{
		for (int i=c[b[r]];i<=d[b[r]];++i)
		if (l<=a[i].id && a[i].id<=r && a[i].n+e[b[i]]<=x)
		++result;
		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()
{
	cin>>n>>m;
	nm=round(sqrt(n));
	for (int i=1;i<=n;++i)
	{
		a[i].id=i;
		scanf("%d",&a[i].n);
		b[i]=(i-1)/nm+1;
		if (b[i]!=b[i-1])
		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--)
	{
		scanf("%d%d%d%d",&k,&x,&y,&z);
		if (k==1)
		{
			if (1<=k && k<=y-x+1)
			{
				l=0x7fffffff;
				r=-0x80000000;
				for (int i=c[b[x]];i<=d[b[x]];++i)
				if (x<=a[i].id && a[i].id<=y)
				{
					l=min(l,a[i].n+e[b[i]]);
					r=max(r,a[i].n+e[b[i]]);
				}
				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)
					{
						l=min(l,a[i].n+e[b[i]]);
						r=max(r,a[i].n+e[b[i]]);
					}
					for (int i=b[x]+1;i<b[y];++i)
					{
						l=min(l,a[c[i]].n+e[i]);
						r=max(r,a[d[i]].n+e[i]);
					}
				}
				ans=r;
				while (l<=r)
				{
					mid=(long long)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
		{
			for (int i=c[b[x]];i<=d[b[x]];++i)
			if (x<=a[i].id && a[i].id<=y)
			a[i].n+=z;
			sort(a+c[b[x]],a+d[b[x]]+1);
			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)
				a[i].n+=z;
				sort(a+c[b[y]],a+d[b[y]]+1);
				for (int i=b[x]+1;i<b[y];++i)
				e[i]+=z;
			}
		}
	}
}