Only 30 pts.

#include<bits/stdc++.h>
#define ll int
#define rg register
using namespace std;
const ll inf=2000000008;
ll be[123456],i,j,n,m,k,x,y,bd;char op;
struct block{
	ll add;
}b[1234];
struct node{
	ll v,l;
}a[1234][1234];
bool cmp(node x,node y)
{
	return x.v<y.v;
}
inline void change(ll x,ll y,ll k)
{
	if(be[x]==be[y])
	{
		for(rg int i=1;i<=bd;i++)
			if(a[be[x]][i].l>=x&&a[be[x]][i].l<=y) a[be[x]][i].v+=k;
		sort(a[be[x]]+1,a[be[x]]+1+bd,cmp);
		return;
	}
	for(rg int i=be[x]+1;i<=be[y]-1;i++) b[i].add+=k;
	for(rg int i=1;i<=bd;i++)
		if(a[be[x]][i].l>=x&&a[be[x]][i].l<=y) a[be[x]][i].v+=k;
	sort(a[be[x]]+1,a[be[x]]+1+bd,cmp);
	for(rg int i=1;i<=bd;i++)
		if(a[be[y]][i].l>=x&&a[be[y]][i].l<=y) a[be[y]][i].v+=k;
	sort(a[be[y]]+1,a[be[y]]+1+bd,cmp);
}
inline ll ask(ll x,ll y,ll k,ll p)
{
	ll ans=0;
	if(be[x]==be[y])
	{
		for(rg int i=1;i<=bd;i++)
			if(a[be[x]][i].l>=x&&a[be[x]][i].l<=y&&a[be[x]][i].v+b[be[x]].add>=k&&a[be[x]][i].v+b[be[x]].add<=inf)
				if(++ans>(y-x+1)-p) return ans;
		return ans;
	}
	for(rg int i=be[x]+1;i<=be[y]-1;i++)
	{
		ll l=1,r=bd,mid;
		while(l<r)
		{
			mid=(l+r)/2;
			if(a[i][mid].v+b[i].add>=k) r=mid;
			else l=mid+1;
		}
		if(a[i][l].v+b[i].add<k) l++;
		ans+=bd-l+1;
		if(ans>(y-x+1)-p) return ans;
	}
	for(rg int i=1;i<=bd;i++)
			if(a[be[x]][i].l>=x&&a[be[x]][i].l<=y&&a[be[x]][i].v+b[be[x]].add>=k&&a[be[x]][i].v+b[be[x]].add<=inf) if(++ans>(y-x+1)-p) return ans;
	for(rg int i=1;i<=bd;i++)
			if(a[be[y]][i].l>=x&&a[be[y]][i].l<=y&&a[be[y]][i].v+b[be[y]].add>=k&&a[be[x]][i].v+b[be[x]].add<=inf) if(++ans>(y-x+1)-p) return ans;
	return ans;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	cin>>n>>m;bd=220;
	memset(a,0x3f,sizeof(a));
	for(i=1;i<=n;i++) be[i]=(i-1)/bd+1;
	for(i=1;i<=n;i++) {cin>>a[(i-1)/bd+1][(i-1)%bd+1].v;a[(i-1)/bd+1][(i-1)%bd+1].l=i;}
	for(i=1;i<=n/bd+1;i++) sort(a[i]+1,a[i]+bd+1,cmp);
	for(i=1;i<=m;i++)
	{
		cin>>op>>x>>y>>k;
		if(op=='2')
		{
			change(x,y,k);
		}
		if(op=='1')
		{
			if(k<1||k>(y-x+1))
			{
				cout<<"-1\n";
				continue;
			}
			ll l=inf,r=-inf;
			for(j=be[x];j<=be[y];j++)
			{
				l=min(l,a[j][1].v+b[j].add);
				r=max(r,(a[j][(j==be[n])?(n%bd):bd].v)+b[j].add);
			}
			r++;
			while(l<r)
			{
				ll mid=(l+r)>>1;
				if((y-x+1)-k<ask(x,y,mid,k)) l=mid+1;
				else r=mid;
			}
			cout<<l-1<<endl;
		}
	}
	return 0;
 }