Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has to cook many dishes today. In between cooking two of them, he decided to relax and play a card game with his friend.

The game is played with cards that have integer *ranks* written on them. There may be multiple cards with the same rank. At the beginning of the game, Chef gets $N$ cards with ranks $a_{1}, a_{2}, \ldots, a_{N}$ and his friend gets $N$ cards with ranks $b_{1}, b_{2}, \ldots, b_{N}$.

The game is played in turns. The players alternate turns and in each turn, one player is the *attacker* and the other is the *defender*. In the first turn, Chef is the attacker. The roles in each subsequent turn depend on the result of the previous turn.

In each turn, the attacker chooses one of his cards and puts it on the table. The defender must either give up this turn or beat this card by choosing one of his cards with a strictly higher rank and putting it on the table. Then, the attacker must give up the turn or choose another of his cards such that its rank is equal to the rank of any card on the table, then the defender must give up or beat this card, and so on until one player gives up the turn. If both players still have cards afterwards, the game proceeds to the next turn with the following rules:
If the attacker gave up, all cards on the table are discarded. In the next turn, the roles of the players are swapped: the attacker becomes the defender and vice versa.
If the defender gave up, he takes all cards on the table, which he can use in the subsequent turns just like the remaining cards which he did not put on the table. In the next turn, the roles are left unchanged.

The game ends when at least one player does not have any cards at the start of some turn. If the attacker gave up the last turn and both players do not have any cards, a draw is announced. Otherwise, the player that ran out of cards wins.

Chef and his friend want to end the game with a draw. Determine if they can do that.

Note that there are two subtasks and your goals in them are different: in the first subtask, Chef does not have much time, so the goal is to get a draw in one turn, while in the second subtask, it is sufficient to get a draw in any number of turns.

------  Input ------
The first line of the input contains two space-separated integers $T$ and $S$ denoting the number of test cases and the subtask. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
The third line contains $N$ space-separated integers $b_{1}, b_{2}, \ldots, b_{N}$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to reach the given goal or "NO" otherwise (without quotes).

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$S \in \{1, 2\}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ a_{i}, b_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (50 points):
$S=1$
the goal is to end the game with a draw in one turn

Subtask #2 (50 points):
$S=2$
the goal is to end the game with a draw in any number of turns

------  Example Input 1 ------

4 1
3
2 1 1
3 2 3
3
4 1 3
3 5 2
3
5 4 6
1 3 2
2
1 1
1 1

------  Example Output 1 ------

YES
NO
NO
NO

------  Example Input 2 ------

4 2
3
2 1 1
3 2 3
3
4 1 3
3 5 2
3
5 4 6
1 3 2
2
1 1
1 1

------  Example Output 2 ------

YES
YES
YES
NO

------  Explanation ------
The only difference between the two examples is that in the first one, $S=1$, while in the second one, $S=2$.

Example case 1: It is possible to reach a draw in one turn if Chef starts by choosing a card with rank $1$, his friend beats it with a card with rank $2$, then Chef chooses a card with rank $2$, his friend beats it with a card with rank $3$, and finally Chef chooses his last card with rank $1$ and his friend beats it with his last card with rank $3$. All cards are discarded afterwards.

Example case 2: At least two turns are necessary to reach a draw. In the first turn, Chef can choose a card with rank $1$, his friend can beat it with a card with rank $3$, then Chef can choose a card with rank $3$ and his friend can beat it with a card with rank $5$. Then, Chef gives up and all these cards are discarded. In the next turn, Chef's friend is the attacker, he chooses the last card with rank $2$ and Chef can beat it with his last card with rank $4$.

Example case 3: The game can end in a draw in five turns as follows:
Chef chooses a card with rank $5$ and his friend gives up and takes it.
Chef chooses a card with rank $4$ and his friend beats it with a card with rank $5$. Chef gives up and both cards are discarded.
Chef's friend chooses a card with rank $1$, Chef takes it.
Chef's friend chooses a card with rank $2$, Chef beats it with a card with rank $6$.
Chef chooses a card with rank $1$ and his friend beats it with a card with rank $3$.

Example case 4: It is impossible to reach a draw at all.

Difficulty: VERY_HARD
Tags: Square root algorithms

Preprocessing

Sweep line algorithms

Game theory

Data structures
Skill types: Data structures

Starter code:

Solutions:
def shift(a, l, r):
	carry = a[l]
	a[l] = a[r]
	for i in range(l + 1, r + 1):
		temp = carry
		carry = a[i]
		a[i] = temp
(t, s) = map(int, input().split())
ans = ['' for i in range(t)]
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	arr.sort()
	brr.sort()
	if s == 1:
		flag = True
		dic1 = {}
		dic2 = {}
		for j in brr:
			dic2[j] = 1
		if brr[0] <= arr[0]:
			flag = False
		else:
			dic1[arr[0]] = 1
			dic1[brr[0]] = 1
			for j in range(1, n):
				try:
					a = dic1[arr[j]]
					if brr[j] <= arr[j]:
						flag = False
						break
					dic1[brr[j]] = 1
				except:
					try:
						a = dic2[arr[j]]
						for k in range(j, n):
							if brr[k] == arr[j]:
								shift(brr, j, k)
						if brr[j] <= arr[j]:
							flag = False
							break
						dic1[arr[j]] = 1
						dic1[brr[j]] = 1
					except:
						flag = False
						break
		if flag:
			ans[i] = 'YES'
		else:
			ans[i] = 'NO'
	else:
		flag = True
		dic = {}
		for j in arr:
			try:
				dic[j] += 1
			except:
				dic[j] = 1
		for j in brr:
			try:
				dic[j] += 1
			except:
				dic[j] = 1
		for j in dic:
			if dic[j] > n:
				flag = False
				break
		if flag:
			asame = 1
			bsame = 1
			asmall = 1
			bsmall = 1
			crr = [0 for j in range(2 * n)]
			counter = 0
			for j in arr:
				crr[counter] = j
				counter += 1
			for j in brr:
				crr[counter] = j
				counter += 1
			crr.sort()
			for j in range(n):
				if crr[j] != arr[j]:
					asmall = 0
					break
			for j in range(n):
				if crr[j] != brr[j]:
					bsmall = 0
					break
			for j in arr:
				if j != arr[0]:
					asame = 0
					break
			for j in brr:
				if j != brr[0]:
					bsame = 0
					break
			if n == 2:
				if arr[1] == brr[0]:
					flag = True
				elif asame == 1 and asmall == 1:
					flag = True
				elif asmall + bsmall == 0:
					flag = True
				else:
					flag = False
			elif bsmall * (asame + bsame) != 0:
				flag = False
		if flag:
			ans[i] = 'YES'
		else:
			ans[i] = 'NO'
for i in ans:
	print(i)


(T, S) = input().split()
T = int(T)
S = int(S)
for _ in range(T):
	n = int(input())
	x = input().split()
	y = input().split()
	for i in range(n):
		x[i] = int(x[i])
		y[i] = int(y[i])
	x.sort()
	y.sort()
	if S == 1:
		if x[n - 1] >= y[n - 1] or x[0] >= y[0]:
			print('NO')
		else:
			f = 0
			for i in range(1, n):
				if x[i - 1] != x[i] and x[i] not in y or x[i] >= y[i]:
					f = 1
					break
			if f == 1:
				print('NO')
			else:
				print('YES')
	elif n == 1:
		if x[0] >= y[0]:
			print('NO')
		else:
			print('YES')
	elif n == 2:
		dictionary = {}
		for i in range(n):
			if x[i] not in dictionary:
				dictionary[x[i]] = 1
			else:
				dictionary[x[i]] += 1
		for i in range(n):
			if y[i] not in dictionary:
				dictionary[y[i]] = 1
			else:
				dictionary[y[i]] += 1
		flag = 0
		for i in dictionary:
			if dictionary[i] > n:
				flag = 1
		if flag == 1:
			print('NO')
		elif x[0] >= y[1] or (y[0] > x[1] and x[1] != x[0]):
			print('NO')
		else:
			print('YES')
	else:
		dictionary = {}
		for i in range(n):
			if x[i] not in dictionary:
				dictionary[x[i]] = 1
			else:
				dictionary[x[i]] += 1
		for i in range(n):
			if y[i] not in dictionary:
				dictionary[y[i]] = 1
			else:
				dictionary[y[i]] += 1
		flag = 0
		for i in dictionary:
			if dictionary[i] > n:
				flag = 1
		if flag == 1:
			print('NO')
		else:
			flag1 = 0
			for i in range(n - 1):
				if x[i] != x[i + 1]:
					flag1 = 1
			if flag1 == 0 and x[0] > y[n - 1]:
				print('NO')
			else:
				flag2 = 0
				for i in range(n - 1):
					if y[i] != y[i + 1]:
						flag2 = 1
				if flag2 == 0 and x[0] > y[n - 1] and (flag1 == 1):
					print('NO')
				else:
					print('YES')


(T, S) = input().split()
T = int(T)
S = int(S)
for _ in range(T):
	n = int(input())
	a = input().split()
	b = input().split()
	for i in range(n):
		a[i] = int(a[i])
		b[i] = int(b[i])
	a.sort()
	b.sort()
	if S == 1:
		if a[n - 1] >= b[n - 1] or a[0] >= b[0]:
			print('NO')
		else:
			flag = 0
			for i in range(1, n):
				if a[i - 1] != a[i] and a[i] not in b or a[i] >= b[i]:
					flag = 1
					break
			if flag == 1:
				print('NO')
			else:
				print('YES')
	elif n == 1:
		if a[0] >= b[0]:
			print('NO')
		else:
			print('YES')
	elif n == 2:
		di = {}
		for i in range(n):
			if a[i] not in di:
				di[a[i]] = 1
			else:
				di[a[i]] += 1
		for i in range(n):
			if b[i] not in di:
				di[b[i]] = 1
			else:
				di[b[i]] += 1
		flag = 0
		for i in di:
			if di[i] > n:
				flag = 1
		if flag == 1:
			print('NO')
		elif a[0] >= b[1] or (b[0] > a[1] and a[1] != a[0]):
			print('NO')
		else:
			print('YES')
	else:
		di = {}
		for i in range(n):
			if a[i] not in di:
				di[a[i]] = 1
			else:
				di[a[i]] += 1
		for i in range(n):
			if b[i] not in di:
				di[b[i]] = 1
			else:
				di[b[i]] += 1
		flag = 0
		for i in di:
			if di[i] > n:
				flag = 1
		if flag == 1:
			print('NO')
		else:
			flag1 = 0
			for i in range(n - 1):
				if a[i] != a[i + 1]:
					flag1 = 1
			if flag1 == 0 and a[0] > b[n - 1]:
				print('NO')
			else:
				flag2 = 0
				for i in range(n - 1):
					if b[i] != b[i + 1]:
						flag2 = 1
				if flag2 == 0 and a[0] > b[n - 1] and (flag1 == 1):
					print('NO')
				else:
					print('YES')


(t, s) = map(int, input().split())
while t > 0:
	t = t - 1
	thisset = set()
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	final_dict = {}
	a_dict = {}
	b_dict = {}
	for i in range(n):
		if a[i] in final_dict:
			final_dict[a[i]] += 1
		else:
			final_dict[a[i]] = 1
		if a[i] in a_dict:
			a_dict[a[i]] += 1
		else:
			a_dict[a[i]] = 1
		if b[i] in final_dict:
			final_dict[b[i]] += 1
		else:
			final_dict[b[i]] = 1
		if b[i] in b_dict:
			b_dict[b[i]] += 1
		else:
			b_dict[b[i]] = 1
	if s == 1:
		flag = 0
		flag1 = 0
		thisset.add(a[0])
		thisset.add(b[0])
		for i in range(n):
			if a[i] >= b[i]:
				flag = 1
			if i == 0:
				continue
			else:
				if a[i] in thisset:
					thisset.add(b[i])
					continue
				else:
					flag = 1
				thisset.add(a[i])
				thisset.add(a[i])
		if flag == 1:
			print('NO')
		else:
			print('YES')
	else:
		max_key = 0
		max_n = -1
		for (key, value) in final_dict.items():
			if max_n < value:
				max_n = value
				max_key = key
		if 2 * n - max_n < max_n:
			print('NO')
		elif n == 1:
			if a[0] >= b[0]:
				print('NO')
			else:
				print('YES')
		elif n == 2:
			if a[0] > b[0] and a[1] > b[1]:
				if a[0] < b[1]:
					print('YES')
				else:
					print('NO')
			elif a[0] < b[0] and a[1] < b[1]:
				if a[0] == a[1] or a[1] >= b[0]:
					print('YES')
				elif a[0] != a[1]:
					print('NO')
				else:
					print('YES')
			else:
				print('YES')
		elif 2 * n - max_n < max_n:
			print('NO')
		elif len(a_dict) == 1:
			if a[0] > b[n - 1]:
				print('NO')
			else:
				print('YES')
		elif len(b_dict) == 1:
			if a[0] > b[n - 1]:
				print('NO')
			else:
				print('YES')
		else:
			print('YES')