A cake assembly line in a bakery was once again optimized, and now $n$ cakes are made at a time! In the last step, each of the $n$ cakes should be covered with chocolate.

Consider a side view on the conveyor belt, let it be a number line. The $i$-th cake occupies the segment $[a_i - w, a_i + w]$ on this line, each pair of these segments does not have common points. Above the conveyor, there are $n$ dispensers, and when a common button is pressed, chocolate from the $i$-th dispenser will cover the conveyor segment $[b_i - h, b_i + h]$. Each pair of these segments also does not have common points.

Cakes and dispensers corresponding to the first example.

The calibration of this conveyor belt part has not yet been performed, so you are to make it. Determine if it's possible to shift the conveyor so that each cake has some chocolate on it, and there is no chocolate outside the cakes. You can assume that the conveyour is long enough, so the cakes never fall. Also note that the button can only be pressed once.

In the first example we can shift the cakes as shown in the picture.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $w$, and $h$ ($1 \le n \le 10^5$; $1 \le w, h \le 10^5$; $h \le w$) — the number of cakes and dispensers, as well as the halfwidths of cakes and segments on which the chocolate is dispensed.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$) — the positions of the cakes centers. It is guaranteed that $a_i + w < a_{i + 1} - w$ for all $i$.

The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($1 \le b_i \le 10^9$) — the positions of the dispensers. It is guaranteed that $b_i + h < b_{i + 1} - h$ for all $i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case output "YES", if it's possible to shift the conveyor in such a way that each cake ends up with some chocolate, and no chocolate is outside the cakes, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.


-----Examples-----

Input
4
3 10 5
65 95 165
40 65 145
5 2 1
1 6 11 16 21
4 9 14 19 24
3 3 2
13 22 29
5 16 25
4 4 1
27 36 127 136
35 50 141 144
Output
YES
YES
NO
YES


-----Note-----

The first example is shown in the figures in the statement.

In the second example, we can move the conveyor, for example, so that the centers of the cakes are at $4, 9, 14, 19, 24$.

In the third example, we can't move the conveyor accordingly.

Difficulty: EASY
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
def decali(tab: list, d):
	res = []
	for i in tab:
		res.append(i + d)
	return res
t = int(input())
l = []
cakes = []
dispensers = []
for i in range(t):
	ch = input()
	a = [int(x) for x in ch.split()]
	l.append(a)
	ch = input()
	a = [int(x) for x in ch.split()]
	cakes.append(a)
	ch = input()
	a = [int(x) for x in ch.split()]
	dispensers.append(a)
for i in range(t):
	n = l[i][0]
	w = l[i][1]
	h = l[i][2]
	cake = cakes[i]
	disp = dispensers[i]
	poss = h <= w
	j = 0
	while j < n and poss:
		if cake[j] - w <= disp[j] - h and cake[j] + w >= disp[j] + h:
			j += 1
		else:
			if cake[j] + w < disp[j] + h:
				cal = disp[j] + h - cake[j] - w
			else:
				cal = disp[j] - h - (cake[j] - w)
			k = 0
			while k < j and poss:
				if cake[k] - w + cal > disp[k] - h or cake[k] + w + cal < disp[k] + h:
					poss = False
				else:
					k += 1
			if poss:
				cake = decali(cake, cal)
			j += 1
	if poss:
		print('YES')
	else:
		print('NO')


import sys

def solve():
	inp = sys.stdin.readline
	(n, w, h) = map(int, inp().split())
	a = list(map(int, inp().split()))
	b = list(map(int, inp().split()))
	r = int(10 ** 9 + 7)
	l = -r
	for i in range(n):
		l = max(l, a[i] - w - b[i] + h)
		r = min(r, a[i] + w - b[i] - h)
	if l <= r:
		print('YES')
	else:
		print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


T = int(input())
for t in range(T):
	(n, w, h) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	c = [a[i] - b[i] for i in range(n)]
	if abs(max(c) - min(c)) <= 2 * (w - h):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, w, h) = map(int, input().split())
	l1 = [int(i) for i in input().split()]
	l2 = [int(i) for i in input().split()]
	l3 = []
	for i in range(n):
		l3.append(l1[i] - l2[i])
	if max(l3) - min(l3) > 2 * (w - h):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	cakes = list(map(int, input().split()))
	dispenser = list(map(int, input().split()))
	status = True
	(a, b) = (float('-inf'), float('inf'))
	for i in range(n):
		a = max(a, cakes[i] - w + h - dispenser[i])
		b = min(b, cakes[i] - dispenser[i] + w - h)
		if a > b:
			print('NO')
			status = False
			break
	if status:
		print('YES')


t = int(input())
for _ in range(t):
	(n, w, h) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	gap = b[0] - h - (a[0] - w)
	flag = True
	new_gap = 0
	for i in range(n):
		a[i] += gap
		if a[i] + w < b[i] + h:
			flag = False
			break
		new_gap = max(new_gap, a[i] - w - (b[i] - h))
	if not flag:
		print('NO')
		continue
	if new_gap == 0:
		print('YES')
		continue
	for i in range(n):
		a[i] -= new_gap
		if a[i] + w < b[i] + h:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input().strip())
	for _ in range(t):
		(n, w, h) = map(int, input().strip().split())
		a = list(map(int, input().strip().split()))
		b = list(map(int, input().strip().split()))
		a = [i - a[0] for i in a]
		b = [i - b[0] for i in b]
		shift = max((x - y for (x, y) in zip(a, b)))
		b = [i + shift for i in b]
		allow = 2 * (w - h)
		if all((y <= x + allow for (x, y) in zip(a, b))):
			print('YES')
		else:
			print('NO')
main()


t = int(input())
for j in range(t):
	temp = input().split()
	(n, w, h) = (int(temp[0]), int(temp[1]), int(temp[2]))
	an = [int(x) for x in input().split()]
	bn = [int(x) for x in input().split()]
	delta = an[0] - bn[0]
	kr = abs(-w + h)
	pos = 2 * kr
	for i in range(pos + 1):
		flag = True
		ancop = an.copy()
		for k in range(len(ancop)):
			ancop[k] = ancop[k] - delta - kr + i
			if abs(ancop[k] - bn[k]) > kr:
				flag = False
				break
		if flag:
			print('YES')
			break
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(N, W, H) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(l, r) = ([], [])
	for i in range(N):
		l.append(A[i] - W - (B[i] - H))
		r.append(A[i] + W - (B[i] + H))
	(L, R) = (l[0], r[0])
	for i in range(N):
		L = max(L, l[i])
		R = min(R, r[i])
	print('YES' if L <= R else 'NO')


for t in range(int(input())):
	(n, w, h) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mov = []
	for i in range(n):
		mov.append([b[i] + h - (a[i] + w), b[i] - h - (a[i] - w)])
	ans = list(mov[0])
	for i in mov:
		ans[0] = max(i[0], ans[0])
		ans[1] = min(i[1], ans[1])
	if ans[0] <= ans[1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(1, n):
		a[i] -= a[0]
		b[i] -= b[0]
	a[0] = 0
	b[0] = 0
	k = h - w
	FLAG = False
	while b[0] + k + h <= a[0] + w:
		flag = True
		for i in range(n):
			if a[i] - w <= b[i] + k - h and a[i] + w >= b[i] + k + h:
				continue
			flag = False
			break
		if flag:
			FLAG = True
			break
		k += 1
	if FLAG:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cake_left = a[0] - w
	cake_right = a[0] + w
	choc_left = b[0] - h
	choc_right = b[0] + h
	move_left_min = max(0, cake_left - choc_left)
	move_left_max = max(0, cake_right - choc_right)
	move_right_min = max(0, -cake_right + choc_right)
	move_right_max = max(0, -cake_left + choc_left)
	p = 'NO'

	def check(pos, a, b):
		k = False
		for i in range(n):
			cake_left = a[i] - w + pos
			cake_right = a[i] + w + pos
			choc_left = b[i] - h
			choc_right = b[i] + h
			if not (cake_left <= choc_left and cake_right >= choc_right):
				k = True
				break
		return k
	pos = move_left_min
	while pos <= move_left_max:
		if check(-pos, a, b):
			pos = pos + 1
		else:
			pos = move_left_max + 1
			p = 'YES'
	if p == 'YES':
		print(p)
	else:
		pos = move_right_min
		while pos <= move_right_max:
			if check(pos, a, b):
				pos = pos + 1
			else:
				pos = move_right_max + 1
				p = 'YES'
		print(p)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	w = inputs[1]
	h = inputs[2]
	list2 = [int(num) for num in input().split()]
	list1 = [int(num) for num in input().split()]
	list3 = []
	for i in range(0, n):
		ds = list1[i] - h
		de = list1[i] + h
		mid1 = de - w
		mid2 = ds + w
		list3.append((mid1, mid2))
	delta1 = list3[0][0] - list2[0]
	delta2 = list3[0][1] - list2[0]
	delta3 = (list3[0][0] + list3[0][1]) // 2 - list2[0]
	flag = 0
	diff = list3[0][1] - list3[0][0]
	flag1 = 0
	for i in range(0, diff + 1):
		delta = list3[0][0] + i - list2[0]
		flag = 0
		for i in range(0, n):
			cmid = list2[i] + delta
			if cmid >= list3[i][0] and cmid <= list3[i][1]:
				pass
			else:
				flag = 1
				break
		if flag == 0:
			print('YES')
			flag1 = 1
			break
	if flag1 == 0:
		print('NO')


T = int(input())
for t in range(T):
	(N, W, H) = [int(x) for x in input().split()]
	cakes = [(int(x) - W, int(x) + W) for x in input().split()]
	cakes = [(l - cakes[0][0], r - cakes[0][0]) for (l, r) in cakes]
	disps = [(int(x) - H, int(x) + H) for x in input().split()]
	disps = [(l - disps[0][0], r - disps[0][0]) for (l, r) in disps]
	diff = cakes[0][1] - 2 * H - cakes[0][0]
	if diff < 0:
		print('NO')
		break
	for d in range(diff + 1):
		for n in range(N):
			(cl, cr) = cakes[n]
			(dl, dr) = disps[n]
			dl += d
			dr += d
			if not (dl >= cl and dr <= cr):
				break
		else:
			print('YES')
			break
	else:
		print('NO')


def solve(a, b, w, h):
	r1 = [0] * len(a)
	r2 = [0] * len(a)
	for ni in range(n):
		r1[ni] = b[ni] - h - (a[ni] - w)
		r2[ni] = a[ni] + w - (b[ni] + h)
	minr1 = min(r1)
	minr2 = min(r2)
	if minr1 + minr2 >= 0:
		return 'YES'
	return 'NO'
t = int(input())
ans = []
for ti in range(t):
	(n, w, h) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ans.append(solve(a, b, w, h))
for a in ans:
	print(a)


t = int(input())
for _ in range(t):
	(n, w, h) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l1 = []
	l2 = []
	for element in a:
		l1.append(element - w)
		l1.append(element + w)
	sh = l1[0] - (b[0] - h)
	for element in b:
		l2.append(sh + element - h)
		l2.append(sh + element + h)
	c = []
	for i in range(2 * n):
		c.append(l1[i] - l2[i])
	(max1, min1) = (0, 1000000000)
	(max2, min2) = (0, 1000000000)
	for i in range(len(c)):
		if i % 2 == 0:
			if c[i] > max1:
				max1 = c[i]
			if c[i] < min1:
				min1 = c[i]
		if i % 2 == 1:
			if c[i] > max2:
				max2 = c[i]
			if c[i] < min2:
				min2 = c[i]
	out = 'YES'
	if max1 > 0:
		if min2 - max1 < 0:
			out = 'NO'
	if min2 < 0:
		if max1 - min2 > 0:
			out = 'NO'
	print(out)


for _ in range(int(input())):
	(n, w, h) = map(int, input().split(' '))
	a = [int(no) for no in input().split()]
	b = [int(no) for no in input().split()]
	c = []
	d = []
	e = []
	f = -9999999999999999
	for i in range(len(a)):
		c.append(a[i] - w)
		c.append(a[i] + w)
		d.append(b[i] - h)
		d.append(b[i] + h)
		e.append(a[i] - w - b[i] + h)
		e.append(a[i] + w - b[i] - h)
		f = max(f, a[i] - w - b[i] + h)
	for i in range(len(c)):
		c[i] -= f
	g = 0
	for i in range(0, len(c) - 1, 2):
		if c[i] > d[i] or c[i + 1] < d[i + 1]:
			g = 1
			break
	if g == 1:
		print('NO')
	else:
		print('YES')


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for i in range(t):
	(n, w, h) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	shift1 = a[0] - w + h - b[0]
	shift2 = shift1 + 2 * (w - h)
	max1 = max2 = -10 ** 5
	for i in range(n):
		max1 = max(max1, a[i] - w + h - b[i] - shift1)
		max2 = max(max2, b[i] + shift2 - (a[i] + w - h))
	print('YES') if max1 + max2 <= 2 * (w - h) else print('NO')


from math import ceil
for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	md = w - h
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = [x - y for (x, y) in zip(a, b)]
	print(['NO', 'YES'][max(d) - min(d) <= md * 2])


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, w, h) = R()
	r = 9000000000.0
	l = -r
	for (x, y) in zip(R(), R()):
		l = max(l, y - x - w + h)
		r = min(r, y - x + w - h)
	print('YNEOS'[l > r::2])


li = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	(n, w, h) = li()
	a = li()
	b = li()
	c = [a[i] - b[i] for i in range(n)]
	print('YES' if max(c) - min(c) <= 2 * (w - h) else 'NO')


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	cake = list(map(int, input().split()))
	dispense = list(map(int, input().split()))
	c = [cake[i] - dispense[i] for i in range(n)]
	if abs(max(c) - min(c) <= 2 * (w - h)):
		print('YES')
	else:
		print('NO')


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, w, h) = R()
	(a, b) = zip(*((y - x - w + h, y - x + w - h) for (x, y) in zip(R(), R())))
	print('YNEOS'[max(a) > min(b)::2])


n_tests = int(input())
res = []
for num_test in range(n_tests):
	(n, w, h) = list(map(int, input().split()))
	big = list(map(int, input().split()))
	small = list(map(int, input().split()))
	big.sort()
	small.sort()
	left = -float('inf')
	right = float('inf')
	for i in range(n):
		left = max(left, big[i] - w + h - small[i])
		right = min(right, big[i] + w - h - small[i])
	if right >= left:
		res.append('YES')
	else:
		res.append('NO')
print('\n'.join(res))


na = lambda : list(map(int, input().split()))
for _ in range(na()[0]):
	(n, w, h) = na()
	a = na()
	b = na()
	l = float('inf')
	r = -l
	for i in range(n):
		l = min(b[i] - a[i], l)
		r = max(b[i] - a[i], r)
	print('YES' if r - l <= 2 * (w - h) else 'NO')


import sys
input = sys.stdin.readline

def exe():
	cakes.sort()
	conveyor.sort()
	cakes_range = [[cakes[i] - w - (cakes[0] - w), cakes[i] + w - (cakes[0] - w)] for i in range(n)]
	conveyor_range = [[conveyor[i] - h - (conveyor[0] - h), conveyor[i] + h - (conveyor[0] - h)] for i in range(n)]
	adjust = 2 * (w - h)
	i = 0
	move = 0
	while i < n and adjust >= 0:
		if cakes_range[i][0] <= conveyor_range[i][0] + move:
			if conveyor_range[i][1] + move <= cakes_range[i][1]:
				adjust = min(adjust, cakes_range[i][1] - (conveyor_range[i][1] + move))
			else:
				return 'NO'
		else:
			adjust -= cakes_range[i][0] - (conveyor_range[i][0] + move)
			move += cakes_range[i][0] - (conveyor_range[i][0] + move)
		i += 1
	if adjust < 0:
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	cakes = list(map(int, input().split()))
	conveyor = list(map(int, input().split()))
	print(exe())


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	cakes = list(sorted(map(int, input().split())))
	mechanisms = list(sorted(map(int, input().split())))
	for i in range(n):
		cakes[i] = (cakes[i] - w, cakes[i] + w)
		mechanisms[i] = (mechanisms[i] - h, mechanisms[i] + h)
	d = mechanisms[0][1] - cakes[0][1]
	a = w * 2 + 1 - h * 2 - 1
	for i in range(1, n):
		if cakes[i][0] + d > mechanisms[i][0]:
			print('NO')
			break
		if cakes[i][1] + d < mechanisms[i][1]:
			diff = mechanisms[i][1] - (cakes[i][1] + d)
			if a < diff:
				print('NO')
				break
			a -= diff
			d += diff
		else:
			a = min(a, mechanisms[i][0] - (cakes[i][0] + d))
	else:
		print('YES')


for _ in range(int(input())):
	(n, w, h) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mn = -1000000000.0
	mx = 1000000000.0
	for i in range(n):
		mx = min(mx, b[i] - h - a[i] + w)
		mn = max(mn, b[i] + h - a[i] - w)
	if mn <= mx:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a == 1:
		b = int(input())
		c = int(input())
		print('YES')
	else:
		arrw = list(map(int, input().split()))
		arrh = list(map(int, input().split()))
		maxv = arrw[0] - arrh[0]
		minv = maxv
		for l in range(1, a):
			if arrw[l] - arrh[l] > maxv:
				maxv = arrw[l] - arrh[l]
			elif arrw[l] - arrh[l] < minv:
				minv = arrw[l] - arrh[l]
		if maxv - minv > 2 * (b - c):
			print('NO')
		else:
			print('YES')