chandu-and-his-girlfriend-returns

In the previous problem Chandu bought some unsorted arrays and sorted them (in non-increasing order). Now, he has many sorted arrays to give to his girlfriend. But, the number of sorted arrays are very large so Chandu decided to merge two sorted arrays into one sorted array. But he is too lazy to do that. So, he asked your help to merge the two sorted arrays into one sorted array (in non-increasing order).

Input:
First line contains an integer T, denoting the number of test cases.
First line of each test case contains two space separated integers N and M, denoting the size of the two sorted arrays.
Second line of each test case contains N space separated integers, denoting the first sorted array A.
Third line of each test case contains M space separated integers, denoting the second array B.

Output:
For each test case, print (N + M) space separated integer representing the merged array.

Constraints:
1 ≤ T ≤ 100
1 ≤ N, M ≤ 5*10^4
0 ≤ Ai, Bi ≤ 10^9

SAMPLE INPUT
1
4 5
9 7 5 3
8 6 4 2 0

SAMPLE OUTPUT
9 8 7 6 5 4 3 2 0

Source: hackerearth | Difficulty: EASY


Solutions:
from collections import defaultdict
count_hash = defaultdict(int)
def merge(arr1, arr2, N, M):
	b = []
	p1=p2=0
	while(p1<N and p2<M):
		if arr1[p1] <= arr2[p2]:
			#print "one ", str(arr1[p1])
			b.append(str(arr1[p1]))
			p1 += 1
		else:
			b.append(str(arr2[p2]))
			#print "two ", str(arr2[p2])
			p2 += 1
	while(p1<N):
		b.append(str(arr1[p1]))
		#print "one ", str(arr1[p1])
		p1 += 1
	while(p2<M):
		b.append(str(arr2[p2]))
		#print "four ", str(arr2[p2])
		p2 += 1
	return b


T = int(input())
while T>0:
	T -= 1
	N, M = list(map(int, input().split(" ")))
	nums1 = []
	nums2 = []
	nums1 = list(map(int, input().split(" ")))
	nums2 = list(map(int, input().split(" ")))
	result = merge(sorted(nums1), sorted(nums2), N, M)
	print(" ".join(result[::-1]))
	



t=int(input())
while t>0:
	inp=input()
	n=int(inp.split(" ")[0])
	m=int(inp.split(" ")[1])
	i=0
	a=[]
	b=[]
	a=input().split(" ")
	b=input().split(" ")
	for i in range(n):
		a[i]=int(a[i])
	for i in range(m):
		b[i]=int(b[i])
	f=0
	s=0
	str=""
	while f<n and s<m:
		if a[f]>=b[s]:
			print(a[f],end=" ")
			f+=1
		elif b[s]>a[f]:
			print(b[s],end=" ")
			s+=1
	if f==n:
		while s<m:
			print(b[s],end=" ")
			s+=1
	if s==m:
		while f<n:
			print(a[f],end=" ")
			f+=1
	print()    
	t-=1


for i in range(eval(input())):
	n,m =list(map(int,input().split(" ")))
	first = list(map(int,input().split(" ")))
	second = list(map(int,input().split(" ")))
	tmp=[]
	p=0
	q=0
	for iterations in range(m+n):
		if p>n-1:
			tmp.append(second[q])
			q+=1
		elif q>m-1:
			tmp.append(first[p])
			p+=1
		elif first[p]>second[q]:
			tmp.append(first[p])
			p+=1
		else:
			tmp.append(second[q])
			q+=1
	print(" ".join(map(str,tmp[::])))


t = eval(input())
while t:
	t-=1
	sizes = input().split()
	a = b = []
	a = input().split()
	a = [int(x) for x in a]
	b = input().split()
	b = [int(x) for x in b]
	a =  sorted(a+b)[::-1]
	for x in a:
		print(x, end=' ')
	print('')


def merge(a,l,m,r):
	L=a[l:m+1]
	R=a[m+1:r+1]
	i=0
	j=0
	k=l
	while i<len(L) and j<len(R):
		 if L[i]>=R[j]:
		     a[k]=L[i]
		     i+=1
		 else:
		     a[k]=R[j]
		     j+=1
		 k+=1

	while i < len(L):
		  a[k]=L[i]
		  k+=1
		  i+=1
	while j < len(R):
		  a[k]=R[j]
		  j+=1
		  k+=1

t=eval(input());
while t > 0:
	t-=1;
	n,m=list(map(int,input().split()));
	A=list(map(int,input().split()));
	B=list(map(int,input().split()));
	C=A+B;
	merge(C,0,n-1,n+m-1);
	for i in C:
		print(i, end=' ')
	print("");


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())
for i in range(t):
	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()]

	c = []
	la = 0
	lb = 0

	while la < n or lb < m:
		if la == len(a):
			a1=-1
		else:
			a1=a[la]

		if lb == len(b):
			b1=-1
		else:
			b1=b[lb]

		if a1>b1:
			c.append(a1)
			la+=1
		else:
			c.append(b1)
			lb+=1
	print(" ".join([str(x) for x in c]))




class Find:
	def merge(self,N,M):
		ar1 = str(input())
		nar1=ar1.split()
		assert(len(nar1)==N)
		ar2 = str(input())
		nar2 = ar2.split()
		assert(len(nar2)==M)
		array1=[]
		array2=[]
		for i in range(len(nar1)):
			array1.append(int(nar1[i]))
		for j in range(len(nar2)):
			array2.append(int(nar2[j]))
		array1.extend(array2)
		array1.sort()
		result=[]

		array1.sort(reverse=True)
		newresult=""
		for i in range(len(array1)):
			newresult+=str(array1[i])
			newresult+=" "
		print(newresult)
		
		







T=int(eval(input()))
assert(1<=T and T<=100)
while T:
	fl=str(input())
	new=fl.split()
	N=int(new[0])
	M=int(new[1])
	assert(1<=N and N<=50000)
	assert(1<=M and M<=50000)
	obj=Find()
	obj.merge(N,M)
	T-=1


def merge(arri, arrj):
	arr = []
	for _ in range(len(arri) + len(arrj)):
		if (not arri) or (arrj and arri[-1] > arrj[-1]):
			arr.append(arrj.pop())
		else:
			arr.append(arri.pop())
	return reversed(arr)
for _ in range(int(input())):
	n, m = list(map(int, input().split()))
	narr = list(map(int, input().split()))
	marr = list(map(int, input().split()))
	print(' '.join(map(str, merge(narr, marr))))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
__author__ = 'sandeepmellacheruvu'

def merge(arr1, arr2):
	merged = [0] * (len(arr1) + len(arr2))
	i = 0
	j = 0
	k = 0
	while(i < len(arr1) and j < len(arr2)):
		if(arr1[i] > arr2[j]):
			merged[k] = arr1[i]
			i += 1
		else:
			merged[k] = arr2[j]
			j += 1
		k += 1
	while(i < len(arr1)):
		merged[k] = arr1[i]
		k += 1
		i += 1
	while(j < len(arr2)):
		merged[k] = arr2[j]
		k += 1
		j += 1
	return merged

T = int(input())
for testcase in range(0, T):
	NM = input()
	N = int(NM.split(" ")[0])
	M = int(NM.split(" ")[1])
	arrStr1 = input()
	arrStr2 = input()
	arr1 = list(map(int, arrStr1.split(" ")))
	arr2 = list(map(int, arrStr2.split(" ")))
	merged = merge(arr1, arr2)
	print((" ".join(map(str, merged))))


def merge(a,b):
	c=[]
	l1=len(a)
	l2=len(b)
	i=0
	j=0
	while i<l1 and j<l2:
		if a[i]>b[j]:
			c.append(a[i])
			i+=1
		else:
			c.append(b[j])
			j+=1
	while i<l1:
		c.append(a[i])
		i+=1
	while j<l2:
		c.append(b[j])
		j+=1
	return c
for t in range(int(input())):
	n,m=list(map(int,input().split()))
	a=list(map(int,input().split()))
	b=list(map(int,input().split()))
	c=merge(a,b)
	for i in c:
		print(i, end=' ')
	print()


t=int(input())
for i in range(t):
	arr=[]
	n,m=list(map(int,input().split()))
	arr1=list(map(int,input().split()))
	arr2=list(map(int,input().split()))
	j=0
	k=0
	ma=max(n,m)
	while(j<n and k<m):
		if(arr1[j]>arr2[k]):			
			arr.append(arr1[j])
			j+=1
			
		else:
			arr.append(arr2[k])			
			k+=1
	
	if(n-j>0):
		while j!=n:
			arr.append(arr1[j])
			j+=1
		
	if(m-k>0):
		while k!=m:
			arr.append(arr2[k])
			k+=1
	
		
		
	print(' '.join(map(str,arr)))
		




t = int(input())
while t > 0:
	t -= 1
	input()
	a = list(map(int, input().split(" ")))
	b = list(map(int, input().split(' ')))
	i = j = k = 0
	arr = [None] * (len(a) + len(b))
	while i < len(a) and j < len(b):
		if a[i] > b[j]:
			arr[k] = a[i]
			i += 1
		elif b[j] > a[i]:
			arr[k] = b[j]
			j += 1
		elif a[i] == b[j]:
			arr[k] = a[i]
			arr[k + 1] = b[j]
			i += 1
			j += 1
			k += 1
		k += 1
	while i < len(a):
		arr[k] = a[i]
		k += 1
		i += 1
	while j < len(b):
		arr[k] = b[j]
		k += 1
		j += 1
	for l in arr:
		print(l, end=' ')
	print('')


def solve(xs, ys):
	res = []
	i, j = 0, 0
	while True:
		if i >= len(xs):
			res.extend(ys[j:])
			break
		if j >= len(ys) or xs[i] > ys[j]:
			res.append(xs[i])
			i += 1
		else:
			res.append(ys[j])
			j += 1
	return ' '.join(str(r) for r in res)
	
if __name__ == '__main__':
	for _ in range(int(input())):
		_ = input()
		xs = list(map(int, input().split()))
		ys = list(map(int, input().split()))
		print(solve(xs, ys))


def merge_sort(a_list):
	
	
	
	if len(a_list)>1:
		mid = len(a_list)/2
		left = a_list[:mid]
		right = a_list[mid:]
		
		merge_sort(left)
		merge_sort(right)
		
		i=0
		j=0
		k=0
		
		ll = len(left)
		lr = len(right)
				
		#Merging lists
		while i<ll and j<lr:
		
			if left[i]>right[j]:
				a_list[k] = left[i]
				i+=1
						
			else:
				a_list[k] = right[j]
				j+=1
			k+=1
		while i<ll:
				a_list[k] = left[i]
				k+=1
				i+=1
		while j<lr:
				a_list[k] = right[j]
				k+=1
				j+=1
	return a_list		
		
t = eval(input())
ip = []
op = []
for i in range(t):
	temp = []
	temp1 = []
	temp2 = []
	n,m = list(map(int,input().split(' ')))
	temp1 = list(map(int,input().split(' ')))
	temp2 = list(map(int,input().split(' ')))
	temp = temp1+temp2
	
	ip.append(temp)

	
for array in ip:
	array = merge_sort(array)
	
	print(' '.join(map(str,array)))


t=eval(input())
for k in range(t):
	n,m=list(map(int,input().split()))
	a=list(map(int,input().split()))
	b=list(map(int,input().split()))
	c=sorted(a+b,reverse=True)
	for i in c:
		print(i, end=' ')
	print() 




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def sort():
	for case in range(eval(input())):
	N, M = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort(reverse = True)
	c = list(map(str, c))
	print(' '.join(c))
	
if __name__ == "__main__":
	sort()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def solve(n,m,A,B):
	res = []
	i = j = 0
	while i < n and j < m:
		if A[i] >= B[j]:
			res.append(str(A[i]))
			i += 1
		else:
			res.append(str(B[j]))
			j += 1
	if i != n:
		for a in A[i:]:
			res.append(str(a))
	elif j != m:
		for b in B[j:]:
			res.append(str(b))
	return ' '.join(res)

def chandu_and_his_girlfriend_returns():	
	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()))
		print(solve(n,m,A,B))

if __name__ == "__main__":
	chandu_and_his_girlfriend_returns()