Given Pointer/Reference to the head of a doubly linked list of N nodes, the task is to Sort the given doubly linked list using Merge Sort in both non-decreasing and non-increasing order.
Example 1:
Input:
N = 8
value[] = {7,3,5,2,6,4,1,8}
Output:
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Explanation: After sorting the given
linked list in both ways, resultant
matrix will be as given in the first
two line of output, where first line
is the output for non-decreasing
order and next line is for non-
increasing order.
Example 2:
Input:
N = 5
value[] = {9,15,0,-1,0}
Output:
-1 0 0 9 15
15 9 0 0 -1
Explanation: After sorting the given
linked list in both ways, the
resultant list will be -1 0 0 9 15
in non-decreasing order and 
15 9 0 0 -1 in non-increasing order.
Your Task:
The task is to complete the function sortDoubly() which sorts the doubly linked list. The printing is done automatically by the driver code.
Constraints:
1 <= N <= 10^{5}

Difficulty: MEDIUM
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:
#User function Template for python3

'''
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

'''
#Function to sort the given doubly linked list using Merge Sort.
def sortDoubly(head):
    #Your code here
    

Solutions:
def sortDoubly(head):
	res = []
	while head:
		res.append(head.data)
		head = head.next
	res.sort()
	val = DoublyLinkedList()
	for i in res:
		val.append(i)
	return val.head


def sortDoubly(head):
	m = []
	s = head
	while s:
		m.append(s.data)
		s = s.next
	s = head
	m.sort()
	while s:
		s.data = m.pop(0)
		s = s.next
	return head


def sortDoubly(head):
	head1 = None
	head2 = None
	a = head
	b = None
	c = None
	p = []
	while a is not None:
		p.append(a.data)
		a = a.next
	for i in sorted(p):
		m = Node(i)
		if head1 is None:
			head1 = m
			a = head1
		else:
			a.next = m
			m.prev = a
			a = a.next
	return head1


def sortDoubly(head):
	li = []
	temp = head
	while temp:
		li.append(temp.data)
		temp = temp.next
	li.sort()
	l3 = DoublyLinkedList()
	for i in li:
		l3.append(i)
	return l3.head


def length(p):
	ans = 0
	while p:
		p = p.next
		ans += 1
	return ans

def merge(left, right):
	head = Node(-1)
	prev = head
	while left or right:
		if not left:
			prev.next = right
			right.prev = prev
			break
		elif not right:
			prev.next = left
			left.prev = prev
			break
		elif left.data < right.data:
			prev.next = left
			left.prev = prev
			prev = left
			left = left.next
		else:
			prev.next = right
			right.prev = prev
			prev = right
			right = right.next
	if head.next:
		head.next.prev = None
	return head.next

def sortDoubly(head):
	if not head:
		return None
	if not head.next:
		return head
	n = length(head)
	half = n // 2
	p = head
	while half > 1:
		p = p.next
		half -= 1
	prev = p
	p = p.next
	prev.next = None
	if p:
		p.prev = None
	left = sortDoubly(head)
	right = sortDoubly(p)
	return merge(left, right)


def merge(head1, head2):
	if head2 == None:
		return head1
	tmp = temp = pre = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				temp.prev = pre
				pre = temp
				tmp = head1
			else:
				tmp.next = head1
				head1.prev = tmp
				pre = head1
				tmp = tmp.next
			head1 = head1.next
		else:
			if not tmp:
				temp = head2
				temp.prev = pre
				tmp = head2
			else:
				tmp.next = head2
				head2.prev = tmp
				pre = head2
				tmp = tmp.next
			head2 = head2.next
	while head1:
		tmp.next = head1
		head1.prev = tmp
		pre = head1
		tmp = tmp.next
		head1 = head1.next
	while head2:
		tmp.next = head2
		head2.prev = tmp
		pre = head2
		tmp = tmp.next
		head2 = head2.next
	return temp

def mergesort(head):
	if head:
		if not head.next:
			return head
		slow = fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		nxt = slow.next
		slow.next = None
		l = mergesort(head)
		r = mergesort(nxt)
		head = merge(l, r)
		return head
	return None

def sortDoubly(head):
	return mergesort(head)


def merge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	node = root = None
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			if root == None:
				node = root = head1
				head1.prev = None
				head1 = head1.next
			else:
				node.next = head1
				node.next.prev = node
				node = node.next
				head1 = head1.next
		elif root == None:
			node = root = head2
			head2.prev = None
			head2 = head2.next
		else:
			node.next = head2
			node.next.prev = node
			node = node.next
			head2 = head2.next
	if head1:
		node.next = head1
		head1.prev = node
	if head2:
		node.next = head2
		head2.prev = node
	return root

def sortDoubly(head):
	if head.next == None or head == None:
		return head
	fast = mid = head
	while fast != None and fast.next != None:
		fast = fast.next.next
		mid = mid.next
	mid.prev.next = None
	mid.prev = None
	left = sortDoubly(head)
	right = sortDoubly(mid)
	return merge(left, right)


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

def merge_sort(a):
	if len(a) > 1:
		mid = len(a) // 2
		L = a[:mid]
		R = a[mid:]
		merge_sort(L)
		merge_sort(R)
		merge(a, L, R)

def sortDoubly(head):
	a = []
	curr = head
	while curr is not None:
		a.append(curr.data)
		curr = curr.next
	merge_sort(a)
	curr = head
	i = 0
	while curr is not None:
		curr.data = a[i]
		i += 1
		curr = curr.next
	return head


def sortDoubly(head):
	temp = head
	res = []
	while temp:
		res.append(temp.data)
		temp = temp.next
	res.sort()
	res1 = sorted(res, reverse=True)
	temp = ans = head
	i = 0
	while temp:
		temp.data = res[i]
		i += 1
		temp = temp.next
	return ans


def findMiddle(head):
	tur = head
	hare = head
	while hare and hare.next:
		tur = tur.next
		hare = hare.next.next
	return tur

def merge(h1, h2):
	dum = Node(0)
	temp = dum
	while h1 and h2:
		if h1.data <= h2.data:
			temp.next = h1
			h1.prev = temp
			h1 = h1.next
		else:
			temp.next = h2
			h2.prev = temp
			h2 = h2.next
		temp = temp.next
	while h1:
		temp.next = h1
		h1.prev = temp
		h1 = h1.next
		temp = temp.next
	while h2:
		temp.next = h2
		h2.prev = temp
		h2 = h2.next
		temp = temp.next
	if dum.next:
		dum.next.prev = None
	return dum.next

def mergeSort(head):
	if head == None or head.next == None:
		return head
	middle = findMiddle(head)
	middle.prev.next = None
	middle.prev = None
	l = mergeSort(head)
	r = mergeSort(middle)
	return merge(l, r)

def sortDoubly(head):
	return mergeSort(head)


def sortDoubly(head):
	l = []
	temp = head
	while temp:
		l.append(temp.data)
		temp = temp.next
	l.sort()
	k = DoublyLinkedList()
	for i in l:
		k.append(i)
	return k.head


def sortDoubly(head):
	l = []
	while head:
		l.append(head.data)
		head = head.next
	l.sort()
	l1 = DoublyLinkedList()
	for i in l:
		l1.append(i)
	return l1.head


def sortDoubly(head):
	a = []
	curr = head
	while curr != None:
		a.append(curr.data)
		curr = curr.next
	a.sort()
	i = 0
	temp = head
	while temp:
		temp.data = a[i]
		i += 1
		temp = temp.next
	return head


def sortDoubly(head):
	b = []
	tmp = head
	while tmp:
		b.append(tmp.data)
		tmp = tmp.next
	b.sort()
	tmp = head
	for i in b:
		tmp.data = i
		tmp = tmp.next
	return head


def sortDoubly(head):
	t = head
	l = []
	while t != None:
		l.append(t.data)
		t = t.next
	l.sort()
	t = head
	for i in l:
		t.data = i
		t = t.next
	return head


def merge(list1, list2):
	if list1 == None:
		return list2
	if list2 == None:
		return list2
	a = list1
	b = list2
	if a.data <= b.data:
		head = a
		tail = a
		a = a.next
	else:
		head = b
		tail = b
		b = b.next
	while a != None and b != None:
		if a.data <= b.data:
			tail.next = a
			a.prev = tail
			tail = a
			a = a.next
		else:
			tail.next = b
			b.prev = tail
			tail = b
			b = b.next
	if a != None:
		tail.next = a
		a.prev = tail
	if b != None:
		tail.next = b
		b.prev = tail
	return head

def findMid(head):
	slow = head
	fast = head
	while fast.next != None and fast.next.next != None:
		slow = slow.next
		fast = fast.next.next
	return slow

def sortDoubly(head):
	if head == None or head.next == None:
		return head
	mid = findMid(head)
	nexttomid = mid.next
	mid.next = None
	nexttomid.prev = None
	left = sortDoubly(head)
	right = sortDoubly(nexttomid)
	return merge(left, right)


def sortDoubly(head):
	ll = DoublyLinkedList()
	ptr = head
	lst = []
	while ptr:
		lst.append(ptr.data)
		ptr = ptr.next
	lst.sort()
	for i in lst:
		ll.append(i)
	return ll.head


def sortDoubly(head):
	if head is None or head.next is None:
		return head
	slow = head
	fast = head
	while fast.next is not None and fast.next.next is not None:
		slow = slow.next
		fast = fast.next.next
	head1 = head
	head2 = slow.next
	slow.next = None
	head2.prev = None
	head1 = sortDoubly(head1)
	head2 = sortDoubly(head2)
	return merge(head1, head2)

def merge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	if head1.data < head2.data:
		head1.next = merge(head1.next, head2)
		head1.next.prev = head1
		head1.prev = None
		return head1
	else:
		head2.next = merge(head1, head2.next)
		head2.next.prev = head2
		head2.prev = None
		return head2


def sortDoubly(head):
	cns = head
	ans = []
	while head != None:
		ans.append(head.data)
		head = head.next
	ans.sort()
	cc = cns
	for x in ans:
		cc.data = x
		cc = cc.next
	return cns


def sortDoubly(head):
	list = []
	t = head
	while t:
		list.append(t.data)
		t = t.next
	list.sort()
	l = DoublyLinkedList()
	for i in list:
		l.append(i)
	return l.head


def sortedMerge(head1, head2):
	head3 = Node(0)
	p1 = head1
	p2 = head2
	p3 = head3
	while p1 or p2:
		if p1 and p2:
			if p1.data > p2.data:
				temp = Node(p2.data)
				p3.next = temp
				temp.prev = p3
				p3 = p3.next
				p2 = p2.next
			else:
				temp = Node(p1.data)
				p3.next = temp
				temp.prev = p3
				p3 = p3.next
				p1 = p1.next
		elif p1:
			temp = Node(p1.data)
			p3.next = temp
			temp.prev = p3
			p3 = p3.next
			p1 = p1.next
		elif p2:
			temp = Node(p2.data)
			p3.next = temp
			temp.prev = p3
			p3 = p3.next
			p2 = p2.next
		else:
			break
	head3.next.prev = None
	return head3.next

def sortDoubly(head):
	if not head or not head.next:
		return head
	slow = head
	fast = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	right = slow.next
	slow.next = None
	left = head
	left = sortDoubly(left)
	right = sortDoubly(right)
	result = sortedMerge(left, right)
	return result


def sortDoubly(head):
	if head is None or head.next is None:
		return head
	mid = getMid(head)
	nextofmid = mid.next
	mid.next.prev = None
	mid.next = None
	left = sortDoubly(head)
	right = sortDoubly(nextofmid)
	sortedlist = sortedmerge(left, right)
	return sortedlist

def sortedmerge(left, right):
	if left is None:
		return right
	if right is None:
		return left
	dummy = Node(0)
	tail = dummy
	while left and right:
		if left.data <= right.data:
			tail.next = left
			left.prev = tail
			left = left.next
		else:
			tail.next = right
			right.prev = tail
			right = right.next
		tail = tail.next
	if left:
		tail.next = left
		left.prev = tail
	if right:
		tail.next = right
		right.prev = tail
	head = dummy.next
	head.prev = None
	return head

def getMid(head):
	if head is None:
		return head
	fast = head
	slow = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	return slow


def sortDoubly(head):
	a = []
	cur = head
	while cur is not None:
		a.append(cur.data)
		cur = cur.next
	a1 = sorted(a)
	l3 = DoublyLinkedList()
	for i in a1:
		l3.append(i)
	return l3.head


def sortDoubly(head):
	a = []
	while head:
		a.append(head.data)
		head = head.next
	a.sort()
	dummy = Node(-1)
	move = dummy
	for i in a:
		new = Node(i)
		move.next = new
		new.prev = move
		move = move.next
	val = dummy.next
	val.prev = None
	return val


def merge(m1, m2, newhead):
	if m1 == None:
		return m2
	if m2 == None:
		return m1
	while m1 and m2:
		if m1.data < m2.data:
			if newhead == None:
				node = Node(m1.data)
				tail = node
				newhead = node
			else:
				node = Node(m1.data)
				tail.next = node
				node.prev = tail
				tail = tail.next
			m1 = m1.next
		else:
			if newhead == None:
				node = Node(m2.data)
				tail = node
				newhead = node
			else:
				node = Node(m2.data)
				tail.next = node
				node.prev = tail
				tail = tail.next
			m2 = m2.next
	while m1:
		node = Node(m1.data)
		tail.next = node
		node.prev = tail
		tail = tail.next
		m1 = m1.next
	while m2:
		node = Node(m2.data)
		tail.next = node
		node.prev = tail
		tail = tail.next
		m2 = m2.next
	return newhead

def merge1(head, l):
	if head == None or head.next == None:
		return head
	a = l // 2 - 1
	n = head
	while a > 0:
		n = n.next
		a -= 1
	b = n.next
	n.next = None
	m1 = merge1(head, l // 2)
	m2 = merge1(b, l - l // 2)
	newhead = None
	return merge(m1, m2, newhead)

def sortDoubly(head):
	l = 0
	n = head
	while n:
		l += 1
		n = n.next
	return merge1(head, l)
	return head


def merge(first, second):
	if first is None:
		return second
	if second is None:
		return first
	if first.data < second.data:
		first.next = merge(first.next, second)
		first.next.prev = first
		first.prev = None
		return first
	else:
		second.next = merge(first, second.next)
		second.next.prev = second
		second.prev = None
		return second

def sortDoubly(head):
	if head is None:
		return head
	if head.next is None:
		return head
	second = split(head)
	head = sortDoubly(head)
	second = sortDoubly(second)
	return merge(head, second)

def split(head):
	fast = slow = head
	while True:
		if fast.next is None:
			break
		if fast.next.next is None:
			break
		fast = fast.next.next
		slow = slow.next
	temp = slow.next
	slow.next = None
	return temp


def sortDoubly(head):
	tail = head
	while tail.next is not None:
		tail = tail.next
	(head, tail) = sort(head, tail)
	return head

def printList1(head, tail):
	temp = head
	while temp is not None:
		print(temp.data, end=' ')
		temp = temp.next
	print()
	temp = tail
	while temp is not None:
		print(temp.data, end=' ')
		temp = temp.prev
	print()

def sort(head, tail):
	if head is None or head.next is None:
		return (head, head)
	(mid, end) = (head, head)
	while end is not None and end.next is not None:
		mid = mid.next
		end = end.next.next
	head_pointer = head.prev
	tail_pointer = tail.next
	head.prev = None
	if head_pointer:
		head_pointer.next = None
	tail.next = None
	if tail_pointer:
		tail_pointer.prev = None
	prev_mid = mid.prev
	prev_mid.next = None
	mid.prev = None
	(head1, tail1) = sort(head, prev_mid)
	(head2, tail2) = sort(mid, tail)
	(head, tail) = merge(head1, tail1, head2, tail2)
	head.prev = head_pointer
	if head_pointer:
		head_pointer.next = head
	tail.next = tail_pointer
	if tail_pointer:
		tail_pointer.prev = tail
	return (head, tail)

def conditionalPrint(head1, tail1, head2, tail2, nodes):
	if head1 == 3 and tail1 == 5 and (head2 == 1) and (tail2 == 9):
		for node in nodes:
			print(node.data, end=' ')
	print()

def merge(head1, tail1, head2, tail2):
	(p1, p2, p3, p4) = (head1.data if head1 else '', tail1.data if tail1 else '', head2.data if head2 else '', tail2.data if tail2 else '')
	cur = None
	if head1.data <= head2.data:
		cur = head1
		head1 = head1.next
	else:
		cur = head2
		head2 = head2.next
	cur_head = cur
	while head1 is not None and head2 is not None:
		if head1.data <= head2.data:
			cur.next = head1
			head1 = head1.next
		else:
			cur.next = head2
			head2 = head2.next
		cur.next.prev = cur
		cur = cur.next
	while head1 is not None:
		cur.next = head1
		head1 = head1.next
		cur.next.prev = cur
		cur = cur.next
	while head2 is not None:
		cur.next = head2
		head2 = head2.next
		cur.next.prev = cur
		cur = cur.next
	return (cur_head, cur)


def getmiddle(head):
	if head == None:
		return head
	slow = head
	fast = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	return slow

def sortedMerge(head1, head2):
	temp1 = head1
	temp2 = head2
	head1 = Node(-1)
	tail = head1
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	while temp1 and temp2:
		if temp1.data <= temp2.data:
			tail.next = temp1
			temp1.prev = tail
			temp1 = temp1.next
		else:
			tail.next = temp2
			temp2.prev = tail
			temp2 = temp2.next
		tail = tail.next
	while temp1 or temp2:
		if temp1:
			tail.next = temp1
			temp1.prev = tail
			temp1 = temp1.next
		if temp2:
			tail.next = temp2
			temp2.prev = tail
			temp2 = temp2.next
		tail = tail.next
	head1 = head1.next
	head1.prev = None
	return head1

def sortDoubly(head):
	if head == None or head.next == None:
		return head
	middle = getmiddle(head)
	nextToMiddle = middle.next
	nextToMiddle.prev = None
	middle.next = None
	left = sortDoubly(head)
	right = sortDoubly(nextToMiddle)
	sortedList = sortedMerge(left, right)
	return sortedList


def sortDoubly(head):
	lis = []
	tmp = head
	while head:
		lis.append(head.data)
		head = head.next
	head = tmp
	for i in sorted(lis):
		tmp.data = i
		tmp = tmp.next
	return head


def sortDoubly(head):
	if head == None or head.next == None:
		return head
	mid = findMid(head)
	left = head
	right = mid.next
	mid.next = None
	left = sortDoubly(left)
	right = sortDoubly(right)
	result = merge(left, right)
	return result

def findMid(head):
	fast = head.next
	slow = head
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
	return slow

def merge(left, right):
	if left == None:
		return right
	if right == None:
		return left
	ans = Node(-1)
	temp = ans
	while left != None and right != None:
		if left.data > right.data:
			temp.next = right
			temp.next.prev = temp
			temp = right
			right = right.next
		else:
			temp.next = left
			temp.next.prev = temp
			temp = left
			left = left.next
	while left:
		temp.next = left
		temp.next.prev = temp
		temp = left
		left = left.next
	while right:
		temp.next = right
		temp.next.prev = temp
		temp = right
		right = right.next
	ans = ans.next
	ans.prev = None
	return ans


def sortDoubly(head):
	root = head
	s = head
	l = []
	while root:
		l.append(root.data)
		root = root.next
	l.sort()
	ll = DoublyLinkedList()
	for kk in l:
		ll.append(kk)
	return ll.head


def sortDoubly(head):
	l = []
	curr = head
	while curr:
		l.append(curr.data)
		curr = curr.next
	l.sort()
	curr = head
	i = 0
	while curr:
		curr.data = l[i]
		i += 1
		curr = curr.next
	return head


def find_middle(head):
	slow = head
	fast = head
	while fast.next != None and fast.next.next != None:
		slow = slow.next
		fast = fast.next.next
	return slow

def sortDoubly(head):
	if head == None or head.next == None:
		return head
	middle_head = find_middle(head)
	middle_head_next = middle_head.next
	middle_head.next = None
	middle_head_next.prev = None
	left_head = sortDoubly(head)
	right_head = sortDoubly(middle_head_next)
	sorted_head = merge(left_head, right_head)
	return sorted_head

def merge(l, r):
	if l == None:
		return r
	if r == None:
		return l
	if l.data <= r.data:
		new_head = Node(l.data)
		smaller_head = merge(l.next, r)
		new_head.next = smaller_head
		smaller_head.prev = new_head
	else:
		new_head = Node(r.data)
		smaller_head = merge(l, r.next)
		new_head.next = smaller_head
		smaller_head.prev = new_head
	return new_head


def sortDoubly(head):
	cur = head
	x = []
	while cur:
		x.append(cur.data)
		cur = cur.next
	x.sort()
	cur = head
	for i in x:
		cur.data = i
		cur = cur.next
	return head


def merge(first, second):
	if first is None:
		return second
	if second is None:
		return first
	if first.data < second.data:
		first.next = merge(first.next, second)
		first.next.prev = first
		first.prev = None
		return first
	else:
		second.next = merge(first, second.next)
		second.next.prev = second
		second.prev = None
		return second

def sortDoubly(head):
	if head is None:
		return head
	if head.next is None:
		return head
	second = split(head)
	head = sortDoubly(head)
	second = sortDoubly(second)
	return merge(head, second)

def split(head):
	fast = slow = head
	while True:
		if fast.next is None:
			break
		if fast.next.next is None:
			break
		fast = fast.next.next
		slow = slow.next
	temp = slow.next
	slow.next = None
	return temp
import sys
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.prev = self.tail
		self.tail.next = new_node
		self.tail = new_node

	def printList(self, node):
		while node.next is not None:
			node = node.next
		while node.prev is not None:
			node = node.prev
		while node is not None:
			print(node.data, end=' ')
			node = node.next
		print()

def printList(node):
	temp = node
	while node is not None:
		print(node.data, end=' ')
		temp = node
		node = node.next
	print()
	while temp:
		print(temp.data, end=' ')
		temp = temp.prev
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		llist = DoublyLinkedList()
		for e in arr:
			llist.append(e)
		llist.head = sortDoubly(llist.head)
		printList(llist.head)
		print()


def sortDoubly(head):
	temp = head
	l = []
	while temp is not None:
		l.append(temp.data)
		temp = temp.next
	l.sort()
	temp = head
	for i in l:
		temp.data = i
		temp = temp.next
	return head
import sys
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.prev = self.tail
		self.tail.next = new_node
		self.tail = new_node

	def printList(self, node):
		while node.next is not None:
			node = node.next
		while node.prev is not None:
			node = node.prev
		while node is not None:
			print(node.data, end=' ')
			node = node.next
		print()

def printList(node):
	temp = node
	while node is not None:
		print(node.data, end=' ')
		temp = node
		node = node.next
	print()
	while temp:
		print(temp.data, end=' ')
		temp = temp.prev
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		llist = DoublyLinkedList()
		for e in arr:
			llist.append(e)
		llist.head = sortDoubly(llist.head)
		printList(llist.head)
		print()


def Merge(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	if head1.data < head2.data:
		temp = Merge(head1.next, head2)
		head1.next = temp
		temp.prev = head1
		return head1
	else:
		temp = Merge(head1, head2.next)
		head2.next = temp
		temp.prev = head2
		return head2

def sortDoubly(head):
	if head == None or head.next == None:
		return head
	pre = None
	slow = head
	fast = head
	while fast != None and fast.next != None:
		pre = slow
		slow = slow.next
		fast = fast.next.next
	pre.next = None
	slow.prev = None
	head1 = sortDoubly(head)
	head2 = sortDoubly(slow)
	return Merge(head1, head2)
import sys
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.prev = self.tail
		self.tail.next = new_node
		self.tail = new_node

	def printList(self, node):
		while node.next is not None:
			node = node.next
		while node.prev is not None:
			node = node.prev
		while node is not None:
			print(node.data, end=' ')
			node = node.next
		print()

def printList(node):
	temp = node
	while node is not None:
		print(node.data, end=' ')
		temp = node
		node = node.next
	print()
	while temp:
		print(temp.data, end=' ')
		temp = temp.prev
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		llist = DoublyLinkedList()
		for e in arr:
			llist.append(e)
		llist.head = sortDoubly(llist.head)
		printList(llist.head)
		print()


def sortDoubly(head):
	a = []
	l = DoublyLinkedList()
	curr = head
	while curr:
		a.append(curr.data)
		curr = curr.next
	a.sort()
	for i in range(len(a)):
		l.append(a[i])
	return l.head


def sortDoubly(head):
	if head != None and head.next != None:
		m = getmiddle(head)
		head = sortDoubly(head)
		m = sortDoubly(m)
		head = merge(head, m)
	return head

def getmiddle(head):
	t = head
	h = head
	while h != None and h.next != None:
		h = h.next.next
		t = t.next
	tail = t.prev
	tail.next = None
	t.prev = None
	return t

def merge(a, b):
	cur1 = a
	cur2 = b
	if cur1 == None:
		return cur2
	if cur2 == None:
		return cur1
	if cur1.data < cur2.data:
		cur1.next = merge(cur1.next, cur2)
		cur1.next.prev = cur1
		cur1.prev = None
		return cur1
	else:
		cur2.next = merge(cur1, cur2.next)
		cur2.next.prev = cur2
		cur2.prev = None
		return cur2
import sys
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.prev = self.tail
		self.tail.next = new_node
		self.tail = new_node

	def printList(self, node):
		while node.next is not None:
			node = node.next
		while node.prev is not None:
			node = node.prev
		while node is not None:
			print(node.data, end=' ')
			node = node.next
		print()

def printList(node):
	temp = node
	while node is not None:
		print(node.data, end=' ')
		temp = node
		node = node.next
	print()
	while temp:
		print(temp.data, end=' ')
		temp = temp.prev
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		llist = DoublyLinkedList()
		for e in arr:
			llist.append(e)
		llist.head = sortDoubly(llist.head)
		printList(llist.head)
		print()


def getMiddle(head):
	slow = head
	fast = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	return slow

def merge(l, r):
	if l is None:
		return r
	if r is None:
		return l
	if l.data < r.data:
		l.next = merge(l.next, r)
		l.next.prev = l
		l.prev = None
		return l
	else:
		r.next = merge(l, r.next)
		r.next.prev = r
		r.prev = None
		return r

def sortDoubly(head):
	if head is None or head.next is None:
		return head
	mid = getMiddle(head)
	nexmid = mid.next
	mid.next = None
	nexmid.prev = None
	left = sortDoubly(head)
	right = sortDoubly(nexmid)
	return merge(left, right)


def sortDoubly(head):
	return mergeSort(head)

def mergeSort(head):
	if head is None or head.next is None:
		return head
	(slow, fast) = (head, head.next)
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	mid_prev = slow
	mid = slow.next
	mid_prev.next = None
	mid.prev = None
	head1 = mergeSort(head)
	head2 = mergeSort(mid)
	return merge(head1, head2)

def merge(head1, head2):
	curr = dummy = Node(0)
	(p1, p2) = (head1, head2)
	while p1 and p2:
		if p1.data <= p2.data:
			curr.next = p1
			p1.prev = curr
			p1 = p1.next
		else:
			curr.next = p2
			p2.prev = curr
			p2 = p2.next
		curr = curr.next
	curr.next = p1 or p2
	if p1:
		p1.prev = curr
	elif p2:
		p2.prev = curr
	dummy.next.prev = None
	return dummy.next


def sortDoubly(head):
	if head.next == None:
		return head

	def split(head):
		if head.next == None:
			return head
		fast = head
		slow = head
		while fast is not None and fast.next is not None:
			fast = fast.next.next
			slow = slow.next
		if fast:
			temp = slow.next
			slow.next.prev = None
			slow.next = None
		else:
			temp = slow
			slow = slow.prev
			temp.prev = None
			slow.next = None
		return temp
	temp = split(head)
	left = sortDoubly(head)
	right = sortDoubly(temp)
	result = None
	while left and right:
		if left.data <= right.data:
			newNode = Node(left.data)
			if result:
				result.next = newNode
				newNode.prev = result
				result = result.next
			else:
				result = newNode
				ans = result
			left = left.next
		else:
			newNode = Node(right.data)
			if result:
				result.next = newNode
				newNode.prev = result
				result = result.next
			else:
				result = newNode
				ans = result
			right = right.next
	while left:
		result.next = left
		left.prev = result
		break
	while right:
		result.next = right
		right.prev = result
		break
	return ans


def sortDoubly(head):

	def split(head):
		if head.next == None:
			return head
		sp = head
		fp = head
		while fp and fp.next:
			sp = sp.next
			fp = fp.next.next
		if fp:
			n = sp.next
			n.prev = None
			sp.next = None
		else:
			n = sp
			sp = sp.prev
			n.prev = None
			sp.next = None
		return (head, n)
	if head.next == None:
		return head
	(l, r) = split(head)
	ll = sortDoubly(l)
	rr = sortDoubly(r)
	ans = None
	while ll and rr:
		if ll.data <= rr.data:
			n = Node(ll.data)
			if ans:
				ans.next = n
				n.prev = ans
				ans = ans.next
			else:
				ans = n
				h1 = ans
			ll = ll.next
		else:
			n = Node(rr.data)
			if ans:
				ans.next = n
				n.prev = ans
				ans = ans.next
			else:
				ans = n
				h1 = ans
			rr = rr.next
	while ll:
		n = Node(ll.data)
		ans.next = n
		n.prev = ans
		ans = ans.next
		ll = ll.next
	while rr:
		n = Node(rr.data)
		ans.next = n
		n.prev = ans
		ans = ans.next
		rr = rr.next
	ans.next = None
	return h1


def findMid(head):
	slow = head
	fast = head.next
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
	return slow

def merge(head1, head2):
	merged = Node(-1)
	temp = merged
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			temp.next = head1
			head1.prev = temp
			head1 = head1.next
		else:
			temp.next = head2
			head2.prev = temp
			head2 = head2.next
		temp = temp.next
	while head1 != None:
		temp.next = head1
		head1.prev = temp
		head1 = head1.next
		temp = temp.next
	while head2 != None:
		temp.next = head2
		head2.prev = temp
		head2 = head2.next
		temp = temp.next
	merged = merged.next
	merged.prev = None
	return merged

def sortDoubly(head):
	if head.next == None:
		return head
	mid = findMid(head)
	head2 = mid.next
	head2.prev = None
	mid.next = None
	newHead1 = sortDoubly(head)
	newHead2 = sortDoubly(head2)
	finalHead = merge(newHead1, newHead2)
	return finalHead


def fd(h):
	(s, f) = (h, h)
	while f.next != None and f.next.next != None:
		s = s.next
		f = f.next.next
	temp = s.next
	s.next = None
	return temp

def sortDoubly(head):
	if head == None or head.next == None:
		return head
	spli = fd(head)
	nh1 = sortDoubly(head)
	nh2 = sortDoubly(spli)
	return merge(nh1, nh2)

def merge(h1, h2):
	if h1 == None:
		return h2
	elif h2 == None:
		return h1
	if h1.data < h2.data:
		h1.next = merge(h1.next, h2)
		h1.next.prev = h1
		h1.prev = None
		return h1
	else:
		h2.next = merge(h1, h2.next)
		h2.next.prev = h2
		h2.prev = None
		return h2


def sortDoubly(head):
	if head == None or head.next == None:
		return head
	(firstHalf, secondHalf) = findMid4Doubly(head)
	hold1 = sortDoubly(firstHalf)
	hold2 = sortDoubly(secondHalf)
	head = sortedMerge4Doubly(hold1, hold2)
	return head

def findMid4Doubly(head):
	slow = head
	fast = head
	temp = head
	prevslow = head
	while fast != None and fast.next != None:
		prevslow = slow
		slow = slow.next
		fast = fast.next.next
	if fast == None:
		slow.prev = None
		prevslow.next = None
		return (head, slow)
	else:
		temp = slow.next
		temp.prev = None
		slow.next = None
		return (head, temp)

def sortedMerge4Doubly(head1, head2):
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	head = tail = None
	if head1.data <= head2.data:
		head = tail = head1
		head1 = head1.next
	else:
		head = tail = head2
		head2 = head2.next
	while head1 != None and head2 != None:
		if head1.data <= head2.data:
			(tail.next, head1.prev) = (head1, tail)
			tail = head1
			head1 = head1.next
		else:
			(tail.next, head2.prev) = (head2, tail)
			tail = head2
			head2 = head2.next
	if head1 == None:
		(tail.next, head2.prev) = (head2, tail)
	else:
		(tail.next, head1.prev) = (head1, tail)
	return head


def link_mid(head):
	(fast, slow) = (head.next, head)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	return slow

def merge_sort(hd1, hd2):
	ans = None
	while hd1 and hd2:
		if hd1.data < hd2.data:
			if ans == None:
				ans = hd1
				nxt = ans
			else:
				nxt.next = hd1
				hd1.prev = nxt
				nxt = nxt.next
			hd1 = hd1.next
		else:
			if ans == None:
				ans = hd2
				nxt = ans
			else:
				nxt.next = hd2
				hd2.prev = nxt
				nxt = nxt.next
			hd2 = hd2.next
	if hd1:
		if ans == None:
			ans = hd1
		else:
			nxt.next = hd1
			hd1.prev = nxt
	if hd2:
		if ans == None:
			ans = hd2
		else:
			nxt.next = hd2
			hd2.prev = nxt
	return ans

def merge(head):
	if head.next == None:
		return head
	mid = link_mid(head)
	temp = mid.next
	mid.next = None
	temp.prev = None
	left = merge(head)
	right = merge(temp)
	return merge_sort(left, right)

def sortDoubly(head):
	return merge(head)


def sortDoubly(head):
	if head == None or head.next == None:
		return head
	h1 = head
	h2 = Csplit(head)
	l1 = sortDoubly(h1)
	l2 = sortDoubly(h2)
	return Cmerge(l1, l2)

def Csplit(head):
	fast = slow = head
	while 1:
		if fast.next == None or fast.next.next == None:
			break
		fast = fast.next.next
		slow = slow.next
	secondHead = slow.next
	secondHead.prev = None
	slow.next = None
	return secondHead

def Cmerge(l1, l2):
	if l1 == None:
		return l2
	elif l2 == None:
		return l1
	if l1.data < l2.data:
		l1.next = Cmerge(l1.next, l2)
		l1.next.prev = l1
		return l1
	else:
		l2.next = Cmerge(l1, l2.next)
		l2.next.prev = l2
		return l2