TLE on #10

/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
// #pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define max(x, y)((x) > (y) ? (x) : (y))
#define min(x, y)((x) < (y) ? (x) : (y))
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define lowbit(x) (x & -x)
// #define sort stable_sort
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], lazy[N], id[N], l[N], r[N], n, T, block, len;
void modify(int L, int R, int k)
{
	int lid = id[L], rid = id[R], limit = min(R, r[lid]);
	FOR(i, L, limit)a[i] += k;
	FOR(i, l[lid], r[lid])b[i] = a[i];
	sort(b + l[lid], b + r[lid] + 1);
	FOR(i, lid + 1, rid - 1)lazy[i] += k;
	if (lid != rid)FOR(i, l[rid], R)a[i] += k;
	if (lid != rid)FOR(i, l[rid], r[rid])b[i] = a[i];
	if (lid != rid)sort(b + l[rid], b + r[rid] + 1);
}
int Min(int L, int R)
{
	int lid = id[L], rid = id[R], limit = min(R, r[lid]), ans = INF;
	FOR(i, L, limit)ans = min(ans, a[i] + lazy[id[i]]);
	FOR(i, lid + 1, rid - 1)ans = min(ans, b[l[i]] + lazy[i]);
	if (lid != rid)FOR(i, l[rid], R)ans = min(ans, a[i] + lazy[id[i]]);
	return ans;
}
int Max(int L, int R)
{
	int lid = id[L], rid = id[R], limit = min(R, r[lid]), ans = -INF;
	FOR(i, L, limit)ans = max(ans, a[i] + lazy[id[i]]);
	FOR(i, lid + 1, rid - 1)ans = max(ans, b[r[i]] + lazy[i]);
	if (lid != rid)FOR(i, l[rid], R)ans = max(ans, a[i] + lazy[id[i]]);
	return ans;
}
int check(int L, int R, int k)
{
	int lid = id[L], rid = id[R], limit = min(R, r[lid]), sum = 0;
	FOR(i, L, limit)sum += (a[i] + lazy[id[i]] <= k);
	FOR(i, lid + 1, rid - 1)
	{
		int _L = l[i], _R = r[i], res = _L - 1;
		if (b[l[i]] + lazy[i] > k)continue;
		while (_L <= _R)
		{
			int mid = (_L + _R) >> 1;
			if (b[mid] + lazy[i] <= k)res = mid, _L = mid + 1;
			else _R = mid - 1;
		}
		sum += res - l[i] + 1;
	}
	if (lid != rid)FOR(i, l[rid], R)sum += (a[i] + lazy[id[i]] <= k);
	return sum;
}
int query(int L, int R, int k)
{
	if (k < 1 || k > R - L + 1)return -1;
	int lid = id[L], rid = id[R], ans = -1, _L = Min(L, R), _R = Max(L, R);
	while (_L <= _R)
	{
		int mid = (_L + _R) >> 1;
		if (check(L, R, mid) >= k)ans = mid, _R = mid - 1;
		else _L = mid + 1;
	}
	return ans;
}
char buf[1 << 20], *p1 = buf, *p2 = buf;
char getch(){return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;}
template <typename T>
void read(T &x)
{
	x = 0; char s = getch(); int f = 1;
	for (; s < '0' || s > '9'; s = getch())if (s == '-')f = -f;
	for (; s >= '0' && s <= '9'; s = getch())x = (x << 3) + (x << 1) + (s ^ 48);
	x *= f;
}
template <typename T, typename ...Args>
void read(T &tmp, Args &...tmps){read(tmp); read(tmps...);}
signed main()
{
	#ifdef Fileopen
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	read(n, T);
	block = 400; len = ceil(1.0 * n / block);
	FOR(i, 1, n)read(a[i]);
	FOR(i, 1, n)b[i] = a[i];
	FOR(i, 1, n)id[i] = (i - 1) / block + 1;
	FOR(i, 1, len)l[i] = (i - 1) * block + 1;
	FOR(i, 1, len)r[i] = i * block;
	r[len] = n;
	FOR(i, 1, len)sort(b + l[i], b + r[i] + 1);
	while (T--)
	{
		int opt, L, R, k; read(opt, L, R, k);
		if (opt == 1)printf("%lld\n", query(L, R, k));
		else modify(L, R, k);
	}
	return 0;
}