*"Stick with the strongest team, that's the only way."*

Gi-Hun and his mates have survived the deadly night, but now it’s time for the tug of war. The game proceeds as follows:

Two teams have to face off against each other in a tug of war match. The match proceeds in a series of rounds as follows:
Initially, one player from each team will come forward to play.
The one who wins the round will stay in, while the loser is eliminated. If the round is a draw, both players are eliminated.
When a member of a team is eliminated, that team then sends another person to play in the next round.
This process continues as long as both teams have at least one player left.

Note that if a player wins their round, they must stay in for the next round — they cannot be replaced by another player.

A team is said to win the match if it has at least 1 player remaining, while all players of the opponent's team are eliminated. If both teams have no players left, the match is said to be a draw.

Gi-Hun has to come up with a strategy for his team to win the game. He saw the opponent queue of N players, where their i^{\text{th}} player has strength A_{i}. He also knows that the opponent will send the players in the same order as they appear in A. Formally for any two players i and j where i<j, player i will always play before player j. He also knows the strength of his M players — the i^{\text{th}} player of his team has strength B_{i}. 

Further, Gi-Hun knows that when two players play against each other, the player with higher strength always wins. If both players have equal strength, the round is a draw.

Now, he wants to know whether they can win a match or not, and if they can, what is the ordering of his team players that will let them win. In case multiple orderings are possible, he would like to know the lexicographically smallest ordering.

An array X is [lexicographically smaller] than an array Y if there exists an index i such that X_{i} < Y_{i}, and X_{j}=Y_{j} for all 1 ≤ j < i. Less formally, at the first index i in which they differ, X_{i} < Y_{i}.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and M — the sizes of the opponent team and Gi-Hun's team, respectively.
- The second line of each test case contains N space-separated integers, A_{1}, A_{2}, \ldots, A_{N} — the strengths of the opponents, in order.
- The third line of each test case contains M space-separated integers, B_{1}, B_{2}, \ldots, B_{M} — the strengths of Gi-Hun's team.

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

- The first line of each test case should contain a single string, either “YES” or “NO”, denoting whether it is possible for Gi-Hun's team to win or not.
- If the first line contains "YES", print a second line containing M space-separated integers — the lexicographically smallest ordering which will allow Gi-Hun's team to win.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N,M ≤ 10^{6}$
$1 ≤ A_{i},B_{j} ≤ 10^{9}$ ($1 ≤ i ≤ N$, $1 ≤ j ≤ M$)
- Sum of $N$ and $M$ across all test cases will not exceed $10^{6}$

----- Sample Input 1 ------ 
5
3 1
4 3 5
6
3 3
2 4 7
2 3 7
3 3
2 7 4
2 7 3
4 4
2 6 5 1
4 6 5 2
2 2
7 4
7 4

----- Sample Output 1 ------ 
YES
6
YES
2 7 3
NO
YES
2 6 5 4
NO

----- explanation 1 ------ 
Test Case 1: There is only one possible ordering, that being $[6]$. The match will proceed as follows:

- Round 1: $B_{1} = 6$ will defeat $A_{1} = 4$, $A_{1}$ is eliminated.
- Round 2: $B_{1} = 6$ will defeat $A_{2} = 3$, $A_{2}$ is eliminated.
- Round 3: $B_{1} = 6$ will defeat $A_{3} = 5$, $A_{3}$ is eliminated.

$B_{1}$ still remains and all opponents have been defeated, making this a victory for Gi-Hun's team.

Test Case 2: The ordering which result in victory are $[2,7,3],[3,7,2],[7,2,3]$, and $[7,3,2]$. Of these, the lexicographically smallest is $[2, 7, 3]$.

Let $Q = [2, 7, 3]$. The match proceeds as follows:
- Round 1: $Q_{1} = 2$ will draw with $A_{1} = 2$, eliminating both.
- Round 2: $Q_{2} = 7$ will defeat $A_{2} = 4$, eliminating $A_{2}$.
- Round 3: $Q_{2} = 7$ will draw with $A_{3} = 7$, eliminating both.

$Q_{3} = 3$ still remains, so Gi-Hun's team wins.

Test Case 3: It is not possible to win the match.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Sorting

Amortized analysis

Complete search

Data structures

Ad-hoc
Skill types: Data structures

Sorting

Amortized analysis

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	bool = True
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	B.sort(reverse=True)
	(flag, i, j) = (0, 0, 0)
	while i < n and j < m:
		if A[i] > B[j]:
			flag = 1
			break
		elif A[i] < B[j]:
			i = i + 1
		else:
			i = i + 1
			j = j + 1
	if flag == 1 or j == m:
		print('NO')
	else:
		ans = B[j + 1:][::-1] + B[:j + 1]
		print('YES')
		print(*ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	ans = []
	l2.sort()
	s = False
	for j in l1:
		if not l2 or l2[-1] < j:
			s = True
			break
		elif l2[-1] == j:
			ans.append(j)
			l2.pop()
	if not l2 or s:
		print('NO')
		continue
	print('YES')
	ans.append(l2.pop())
	print(*l2, *ans)


import sys
for t in range(int(input())):
	(n, m) = map(int, input().split())
	lst_n = list(map(int, input().split()))
	lst_m = list(map(int, input().split()))
	ans = []
	lst_m.sort()
	flag = False
	for x in lst_n:
		if not lst_m or lst_m[-1] < x:
			flag = True
			break
		elif lst_m[-1] == x:
			ans.append(x)
			lst_m.pop()
	if not lst_m or flag:
		print('NO')
		continue
	print('YES')
	ans.append(lst_m.pop())
	print(*lst_m, *ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	b.sort(reverse=True)
	i = 0
	j = 0
	f = True
	while i < n and j < m:
		if a[i] < b[j]:
			i += 1
		elif a[i] == b[j]:
			i += 1
			j += 1
		else:
			f = False
			break
	if j == m:
		f = False
	if f:
		print('YES')
		for i in b[j + 1:m][::-1]:
			print(i, end=' ')
		for i in b[:j + 1]:
			print(i, end=' ')
		print()
	else:
		print('NO')


test = int(input())
while test:
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	b.sort(reverse=True)
	i = j = 0
	found = 1
	while i < len(a) and j < len(b):
		if b[j] < a[i]:
			found = 0
			break
		elif b[j] > a[i]:
			i += 1
		else:
			i += 1
			j += 1
	if found == 0 or len(b) == j:
		print('NO')
	else:
		k = b[-1:j:-1] + b[0:j + 1]
		print('YES')
		print(*k)
	test -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b = sorted(b)
	i = 0
	j = m - 1
	f = 0
	while i < n and j >= 0:
		if a[i] > b[j]:
			print('NO')
			f = 1
			break
		elif a[i] < b[j]:
			i += 1
		else:
			i += 1
			j -= 1
	if j == -1:
		print('NO')
	elif not f:
		print('YES')
		for k in range(j):
			print(b[k], end=' ')
		for k in range(m - 1, j - 1, -1):
			print(b[k], end=' ')
		print()


def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	B.sort()
	(i, j) = (0, m - 1)
	while i < n and j >= 0:
		if A[i] > B[j]:
			print('NO')
			return
		elif A[i] < B[j]:
			i += 1
		else:
			i += 1
			j -= 1
	if j == -1:
		print('NO')
		return
	else:
		print('YES')
		for k in range(j):
			print(B[k], end=' ')
		for k in range(m - 1, j - 1, -1):
			print(B[k], end=' ')
		print()
		return
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort(reverse=True)
	(i, j, f) = (0, 0, True)
	while i < n and j < m:
		if a[i] > b[j]:
			f = False
			break
		elif a[i] < b[j]:
			i += 1
		else:
			i += 1
			j += 1
		if j == m:
			f = False
	if not f:
		print('NO')
	else:
		print('YES')
		print(*sorted(b[j + 1:]) + b[:j + 1])


from collections import Counter
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort()
	done = False
	ansArr = []
	while not done:
		la = len(a)
		lb = len(b)
		if la == 0 and lb == 0:
			ans = 'NO'
			break
		if lb == 0:
			ans = 'NO'
			break
		if la == 0:
			ans = 'YES'
			ansArr = b[:-1] + ansArr + [b[-1]]
			break
		ma = max(a)
		mb = max(b)
		if ma > mb:
			ans = 'NO'
			break
		if mb > ma:
			ans = 'YES'
			ansArr = b[:-1] + ansArr + [b[-1]]
			break
		f = a.index(ma)
		a = a[f + 1:]
		ansArr += [mb]
		b = b[:-1]
	print(ans)
	if ans == 'YES':
		for i in ansArr:
			print(i, end=' ')
		print()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr1 = list(map(int, input().split()[:n]))
	arr2 = list(map(int, input().split()[:m]))
	arr2.sort()
	i = j = 0
	ans = []
	while i < n:
		if j == m:
			print('NO')
			break
		elif arr1[i] < arr2[m - j - 1]:
			i += 1
		elif arr1[i] > arr2[m - j - 1]:
			ans.append(arr2[m - j - 1])
			j += 1
		else:
			ans.append(arr2[m - j - 1])
			i += 1
			j += 1
	if i == n:
		if j != m:
			print('YES')
			ans.append(arr2[m - j - 1])
			for i in range(m - j - 1):
				print(arr2[i], end=' ')
			for item in ans:
				print(item, end=' ')
			print()
		else:
			print('NO')


def func():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort()
	j = m - 1
	flg = True
	req = []
	for i in range(n):
		if a[i] == b[j]:
			req.append(b[j])
			j -= 1
			if j < 0:
				flg = False
				break
		elif b[j] < a[i]:
			flg = False
			break
	if flg:
		ans = b[:j] + req + [b[j]]
		print('YES')
		print(*ans)
	else:
		print('NO')
t = int(input())
for i in range(t):
	func()


from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dic_b = defaultdict(lambda : 0)
	dic_a = defaultdict(lambda : 0)
	for y in b:
		dic_b[y] += 1
	mx = 0
	for x in reversed(a):
		if x < mx:
			pass
		else:
			dic_a[x] += 1
			mx = x
	keys_a = sorted(dic_a.keys(), reverse=True)
	keys_b = sorted(dic_b.keys(), reverse=True)
	len_a = len(keys_a)
	len_b = len(keys_b)
	i = 0
	while True:
		if i == min(len_a, len_b):
			if len_a < len_b:
				answer = 'YES'
				v_a = 0
				k_b = keys_b[i]
				v_b = dic_b[k_b]
			else:
				answer = 'NO'
			break
		k_a = keys_a[i]
		k_b = keys_b[i]
		if k_a > k_b:
			answer = 'NO'
			break
		elif k_a < k_b:
			answer = 'YES'
			v_a = 0
			v_b = dic_b[k_b]
			break
		v_a = dic_a[k_a]
		v_b = dic_b[k_b]
		if v_a > v_b:
			answer = 'NO'
			break
		elif v_a < v_b:
			answer = 'YES'
			break
		i = i + 1
	print(answer)
	if answer == 'YES':
		answer = []
		for j in reversed(range(i + 1, len_b)):
			answer.extend([keys_b[j]] * dic_b[keys_b[j]])
		answer.extend([keys_b[i]] * (v_b - v_a - 1))
		for j in range(i):
			answer.extend([keys_b[j]] * dic_b[keys_b[j]])
		answer.extend([keys_b[i]] * (v_a + 1))
		print(' '.join(map(str, answer)))


from math import ceil, gcd, factorial, sqrt, floor
import queue
import re
from itertools import permutations, combinations, accumulate
from collections import Counter, deque
from sys import stdin, stdout
from bisect import bisect, insort, bisect_left, insort_left

def sieve(meta_path):
	prime = [True] * (meta_path + 1)
	p = 2
	while p * p <= meta_path:
		if prime[p] == True:
			for l1 in range(p * p, meta_path + 1, p):
				prime[l1] = False
		p += 1
	return prime

def simplesieve(meta_path):
	prime = [2]
	mark = [False] * (meta_path + 1)
	for p in range(3, meta_path + 1, 2):
		if mark[p] == False:
			prime.append(p)
			if p * p <= meta_path:
				for l1 in range(p * p, meta_path + 1, 2 * p):
					mark[l1] = True
	return mark

def segementedsieve(low, high):
	limit = int(sqrt(high))
	primes = simplesieve(limit)
	prime = [True] * (high - low + 1)
	for l1 in primes:
		lower = low // l1
		if lower <= 1:
			lower = l1 + l1
		elif low % l1 != 0:
			lower = lower * l1 + l1
		else:
			lower = lower * l1
		for l2 in range(lower, high + 1, l1):
			prime[l2 - low] = False
	s1 = []
	s = 0
	for l in range(low, high + 1):
		if prime[l - low]:
			s1.append(l)
	return s1

def isprime(meta_path):
	if meta_path == 2:
		return True
	if meta_path % 2 == 0 or meta_path == 1:
		return False
	for l1 in range(3, int(meta_path ** 0.5) + 1, 2):
		if meta_path % l1 == 0:
			return False
	return True

def binpow(s1, s2, s):
	r2 = 1
	s1 = s1 % s
	while s2 > 0:
		if s2 & 1:
			r2 = r2 * s1 % s
		s1 = s1 * s1 % s
		s2 >>= 1
	return r2

def lcm(s1, s2):
	return s1 // gcd(s1, s2) * s2

def gcdExtended(s1, s2):
	if s2 == 0:
		return (s1, 1, 0)
	(g, x1, y1) = gcdExtended(s2, s1 % s2)
	l1 = y1
	l2 = x1 - s1 // s2 * y1
	return (g, l1, l2)

def dfs(graph, s, l1):
	v = [0] * (s + 1)
	v[l1] = 1
	s1 = [l1]
	z = 0
	while s1 != []:
		l = s1.pop()
		for l1 in graph[l]:
			if v[l1] == 0:
				v[l1] = 1
				s1.append(l1)
	return 'no'

def bfs(graph, n, a, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[a] = 0
	v[a] = 1
	q = queue.Queue()
	q.put(a)
	while not q.empty():
		z = q.get()
		for i in graph[z]:
			if v[i] == 0:
				v[i] = 1
				d[i] = d[z] + 1
				q.put(i)
	return d[dest]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort(reverse=True)
	i = j = 0
	while i < n and j < m:
		if a[i] < b[j]:
			i += 1
		elif a[i] > b[j]:
			j += 1
		else:
			i += 1
			j += 1
	if j == m:
		print('NO')
	else:
		ans = []
		for i in range(m - 1, j, -1):
			ans.append(b[i])
		for i in range(j + 1):
			ans.append(b[i])
		print('YES')
		for i in ans:
			print(i, end=' ')
		print()


from sys import stdin
input = stdin.readline

def answer():
	front = b[:]
	back = [front.pop()]
	ind = 1
	for i in range(m - 1):
		if back[-1] > suf[ind]:
			print('YES')
			print(*front + back)
			return
		if back[-1] < suf[ind]:
			print('NO')
			return
		x = d[suf[ind]].pop()
		while x <= ind - 2:
			x = d[suf[ind]].pop()
		back.append(front.pop())
		ind = x + 2
	ans = front + back
	(i, j) = (0, 0)
	while i < m and j < n:
		if ans[i] > a[j]:
			j += 1
		elif ans[i] < a[j]:
			i += 1
		else:
			i += 1
			j += 1
	if i >= m:
		print('NO')
		return
	print('YES')
	print(*ans)
for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = sorted(list(map(int, input().split())))
	d = dict()
	suf = [-1] * (n + 2)
	for i in range(n - 1, -1, -1):
		suf[i + 1] = max(suf[i + 2], a[i])
		d[a[i]] = d.get(a[i], []) + [i]
	answer()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	B.sort()
	srt = sorted(A)
	i = j = 0
	while i < n and j < m:
		if srt[i] == B[j]:
			i += 1
			j += 1
		elif srt[i] > B[j]:
			j += 1
		else:
			i += 1
	if i == n:
		if j < m:
			print('YES')
			print(*B)
		else:
			(i, j) = (0, m - 1)
			res = []
			while i < n and j >= 0:
				if A[i] < B[j]:
					i += 1
				elif A[i] == B[j]:
					res.append(B[j])
					i += 1
					j -= 1
				else:
					j -= 1
			if j >= 0:
				B = B[:j] + res + [B[j]]
				print('YES')
				print(*B)
			else:
				print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ni = list(map(int, input().split()))
	mi = list(map(int, input().split()))
	mi.sort()
	maxi = ni[-1]
	li = [maxi]
	for i in range(n - 2, -1, -1):
		if ni[i] >= maxi:
			maxi = ni[i]
			li.append(maxi)
	f = 1
	k = m - 1
	x = len(li)
	for i in range(x):
		if li[x - 1 - i] > mi[k]:
			f = 0
			break
		elif li[x - 1 - i] < mi[k]:
			f = 1
			break
		else:
			k = k - 1
			if k < 0:
				f = 0
				break
	if f:
		print('YES')
		for i in range(k):
			print(mi[i], end=' ')
		for i in range(m - 1, k - 1, -1):
			print(mi[i], end=' ')
		print()
	else:
		print('NO')


T = int(input())
for t in range(T):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	if max(b) < max(a):
		print('NO')
	elif max(b) > max(a):
		print('YES')
		b.sort()
		print(*b, sep=' ')
	else:
		mx = []
		for i in range(n):
			mx.append([-1, -1])
		mx[n - 1] = [a[n - 1], n - 1]
		i = n - 2
		while i >= 0:
			if a[i] >= mx[i + 1][0]:
				mx[i] = [a[i], i]
			else:
				mx[i] = [mx[i + 1][0], mx[i + 1][1]]
			i -= 1
		decrease = [i for i in b]
		decrease.sort(reverse=True)
		ans = []
		i = 0
		j = 0
		found = True
		while i != n and j != m:
			num = mx[i][0]
			idx = mx[i][1]
			if num > decrease[j]:
				found = False
				break
			elif num < decrease[j]:
				found = True
				break
			else:
				ans.append(num)
				i = idx + 1
			j += 1
		if not found:
			print('NO')
		else:
			l = len(ans)
			if l == m:
				print('NO')
			else:
				answer = [i for i in decrease[l + 1:]]
				answer = answer[::-1]
				answer.extend(ans)
				answer.append(decrease[l])
				print('YES')
				print(*answer, sep=' ')


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	a_inp = input().split()
	b_inp = input().split()
	a = [int(i) for i in a_inp]
	b = [int(i) for i in b_inp]
	b = sorted(b)
	mex = -1
	final_a = []
	for i in range(n - 1, -1, -1):
		if a[i] >= mex:
			mex = a[i]
			final_a.append(a[i])
	final_a = final_a[::-1]
	flag = True ^ False
	curr_b = m - 1
	for i in final_a:
		if b[curr_b] > i:
			break
		if b[curr_b] < i:
			print('NO')
			flag = False
			break
		else:
			if curr_b == 0:
				print('NO')
				flag = False
				break
			curr_b -= 1
	if flag != 0:
		b_new = []
		for i in range(0, curr_b):
			b_new.append(b[i])
		for i in range(m - 1, curr_b - 1, -1):
			b_new.append(b[i])
		print('YES')
		print(' '.join([str(i) for i in b_new]))


t = int(input())

def str_arr(a):
	return ' '.join(map(str, a))
for _ in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	a = [int(i) for i in input().strip().split()]
	b = [int(i) for i in input().strip().split()]
	b.sort()
	cur_max = -float('inf')
	a_eff = []
	for i in range(n - 1, -1, -1):
		if a[i] >= cur_max:
			cur_max = a[i]
			a_eff.append(a[i])
	a_eff = a_eff[::-1]
	flag = True
	b_pointer = m - 1
	for i in a_eff:
		if b[b_pointer] > i:
			break
		if b[b_pointer] < i:
			print('NO')
			flag = False
			break
		else:
			if b_pointer == 0:
				print('NO')
				flag = False
				break
			b_pointer -= 1
	if flag:
		b_new = []
		print('YES')
		for i in range(0, b_pointer):
			b_new.append(b[i])
		for i in range(m - 1, b_pointer - 1, -1):
			b_new.append(b[i])
		print(str_arr(b_new))


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	(n, m) = [int(x) for x in input().split()]
	opponent_lineup = [int(x) for x in input().strip().split()]
	lineup = [int(x) for x in input().split()]
	lineup.sort()
	j = len(lineup) - 1
	ans = []
	can_win = True
	for opponent in opponent_lineup:
		if lineup[j] == opponent:
			ans += [lineup[j]]
			j -= 1
			if j < 0:
				can_win = False
				break
		elif lineup[j] < opponent:
			can_win = False
			break
	if can_win:
		ans = lineup[:j] + ans + [lineup[j]]
		print('YES')
		print(*ans)
	else:
		print('NO')


I = lambda : list(map(int, input().split()))
from collections import Counter as cc
(t,) = I()
for _ in range(t):
	(n, m) = I()
	ar = I()
	l = sorted(I())
	srt = sorted(ar)
	pos = 1
	j = i = 0
	while i < n and j < m:
		if srt[i] == l[j]:
			j += 1
			i += 1
		elif srt[i] > l[j]:
			j += 1
		else:
			i += 1
	if i == n:
		if j < m:
			print('YES')
			print(*l)
		else:
			i = 0
			j = m - 1
			rem = []
			while i < n and j >= 0:
				if ar[i] < l[j]:
					i += 1
				elif ar[i] == l[j]:
					rem.append(l[j])
					i += 1
					j -= 1
				else:
					j = -1
					break
			if j >= 0:
				l = l[:j] + rem + [l[j]]
				print('YES')
				print(*l)
			else:
				print('NO')
	else:
		print('NO')