There are two merchants in the market. Initially, the first merchant has N items for sale at distinct prices A_{1}, A_{2}, \ldots, A_{N} and the second merchant has M items for sale at distinct prices B_{1}, B_{2}, \ldots, B_{M}.

If you buy an item from a merchant, the prices of all remaining items for both merchants change in the following manner:
The cost of all the remaining items of the chosen merchant will increase by 1. 
The cost of all the remaining items of the other merchant will decrease by 1. 

Note that prices may become negative during this process.

For e.g. if A = [3, 4, 5], B = [1, 3, 4] and you buy the second item from the second merchant then the prices of remaining items will be as follows A = [2, 3, 4], B = [2, -, 5]

You can only buy an item if its cost is at most C. Can you buy all items from both merchants in the market in some order?

------ Input Format ------ 

- The first line of the input contains a single integer T - the number of test cases. The description of T test cases follows.
- The first line of each test case contains three integers N, M and C - the number of items of the first merchant, the number of items of the second merchant and the maximum cost of an item you can buy respectively.
- The second line contains N space-separated integers A_{1} < A_{2} < \cdots < A_{N} - the prices of items of first merchant.
- The third line contains M space-separated integers B_{1} < B_{2} < \cdots < B_{M} - the prices of items of second merchant.

------ Output Format ------ 

For each test case, output Yes if it is possible to buy all items from both merchants in the market in some order. Otherwise, output No.

You may print each character of Yes and No in uppercase or lowercase (for example, the strings yEs, yes, Yes and YES will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i}, B_{i}, C ≤ 10^{9}$
$A_{i} < A_{i + 1}$ for all $1 ≤ i < N$
$B_{i} < B_{i + 1}$ for all $1 ≤ i < M$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$
- the sum of $M$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
6
1 2 1
1
1 2
2 1 2
1 2
1
3 2 5
1 2 4
4 9
3 3 7
2 4 8
1 4 8
5 10 27
3 6 17 28 30
1 3 4 5 7 9 21 27 29 30
9 4 21
1 5 6 8 14 16 19 22 25
2 9 23 27
----- Sample Output 1 ------ 
YES
YES
NO
YES
YES
NO
----- explanation 1 ------ 
Test case 1: One possible sequence of operations is shown below. The item we purchase in a given turn is highlighted in red.

- $A = [{\color{red}1}], B = [1, 2]$
- $A = [-], B = [0, {\color{red}1}]$
- $A = [-], B = [{\color{red}1}, -]$

Test case 2:  One possible sequence of operations is shown below. The item we purchase in a given turn is highlighted in red.

- $A = [1, {\color{red}2}], B = [1]$
- $A = [{\color{red}2}, -], B = [0]$
- $A = [-, -], B = [{\color{red}-1}]$

Note that prices may become $\textbf{negative}$ during this process and in such a case the item can still be bought.

Test case 3: It can be shown that there is no way to buy the second item sold by Merchant $2$ regardless of the order in which we buy the items.

Test case 4: One possible sequence of operations is shown below. The item we purchase in a given turn is highlighted in red.

- $A = [{\color{red}2}, 4, 8], B = [1, 4, 8]$
- $A = [-, 5, 9], B = [0, 3, {\color{red}7}]$
- $A = [-, 4, 8], B = [1, {\color{red}4}, -]$
- $A = [-, 3, {\color{red}7}], B = [2, -, -]$
- $A = [-, {\color{red}4}, -], B = [1, -, -]$
- $A = [-, -, -], B = [{\color{red}0}, -, -]$

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def solve(a, b):
	diff = max(0, a[-1] - c)
	return diff < len(b) and (diff == 0 or b[diff - 1] <= c) and (b[-1] + diff - len(a) <= c)
for t in range(int(input())):
	(n, m, c) = map(int, input().split())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	print('YES' if solve(x, y) or solve(y, x) else 'NO')


def solve(a, b, cost):
	n = len(a)
	m = len(b)
	diff = max(a[-1] - cost, 0)
	if a[-1] > cost and diff > m:
		return False
	if b[-1] + diff - cost > n:
		return False
	if diff > 0 and b[diff - 1] > cost:
		return False
	return True
t = int(input().strip())
while t > 0:
	t -= 1
	(n, m, c) = map(int, input().strip().split())
	arr1 = list(map(int, input().strip().split()))
	arr2 = list(map(int, input().strip().split()))
	if solve(arr1, arr2, c) or solve(arr2, arr1, c):
		print('YES')
	else:
		print('NO')


def solveBasic():
	if A[-1] <= C:
		return 'YES' if B[-1] - N <= C else 'NO'
	elif B[-1] <= C:
		return 'YES' if A[-1] - M <= C else 'NO'
	else:
		(needA, needB) = (A[-1] - C, B[-1] - C)
		return 'YES' if needA <= M and B[needA - 1] <= C and (B[-1] + needA - N <= C) or (needB <= N and A[needB - 1] <= C and (A[-1] + needB - M <= C)) else 'NO'
for _ in range(int(input())):
	(N, M, C) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	print(solveBasic())


import bisect
for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	l = list(map(int, input().split()))
	a = list(map(int, input().split()))
	al = bisect.bisect_right(l, c)
	aa = bisect.bisect_right(a, c)
	x = l[-1] - c
	y = a[-1] - c
	ele = 0
	if x >= 0 and y >= 0:
		ele = x + y
	elif x >= 0:
		ele = x
	elif y >= 0:
		ele = y
	if x <= aa and ele <= n or (y <= al and ele <= m):
		print('YES')
	else:
		print('NO')


def sol(na, nb, a, b, c):
	extra = a[-1] - c
	if extra <= 0:
		if b[-1] - na <= c:
			return 1
		else:
			return 0
	else:
		n = 0
		for i in range(nb):
			if b[i] > c:
				n = i
				break
		if n < extra:
			return 0
		elif b[-1] - na + extra <= c:
			return 1
		else:
			return 0
t = int(input())
for ijkl in range(t):
	(na, nb, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = max(sol(na, nb, a, b, c), sol(nb, na, b, a, c))
	d = {0: 'NO', 1: 'YES'}
	print(d[ans])