Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is head.
Each of the sub-linked-list is in sorted order.
Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 
Note: The flattened list will be printed using the bottom pointer instead of next pointer.
 
Example 1:
Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)
 
Example 2:
Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.
(Note: | represents the bottom pointer.)
 
Your Task:
You do not need to read input or print anything. Complete the function flatten() that takes the head of the linked list as input parameter and returns the head of flattened link list.
 
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
 
Constraints:
0 <= N <= 50
1 <= M_{i} <= 20
1 <= Element of linked list <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3





'''



class Node:

    def __init__(self, d):

        self.data=d

        self.next=None

        self.bottom=None

        

'''

class Solution():

    

    def flatten(self,root):

        #Your code here

Solutions:
class Solution:

	def flatten(self, root):
		if root is None or root.next is None:
			return root
		return self.merge(root, self.flatten(root.next))

	def merge(self, r1, r2):
		if r1 is None or r2 is None:
			return r1 or r2
		tmp = None
		if r1.data < r2.data:
			tmp = r1
			tmp.bottom = self.merge(r1.bottom, r2)
		else:
			tmp = r2
			tmp.bottom = self.merge(r1, r2.bottom)
		tmp.next = None
		return tmp


class Solution:

	def flat(self, head1, head2):
		if not head1 and (not head2):
			return None
		if not head1:
			return head2
		if not head2:
			return head1
		if head1.data <= head2.data:
			head1.bottom = self.flat(head1.bottom, head2)
			return head1
		head2.bottom = self.flat(head2.bottom, head1)
		return head2

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		return self.flat(self.flatten(root.next), root)


class Solution:

	def flatten(self, root):
		l = []
		curr = root
		while curr:
			curr1 = curr
			while curr1 is not None:
				l.append(curr1.data)
				curr1 = curr1.bottom
			curr = curr.next
		l.sort()
		dummy = Node(-1)
		ind = dummy
		for i in l:
			dummy.bottom = Node(i)
			dummy = dummy.bottom
		return ind.bottom


class Solution:

	def flatten(self, root):
		lis = []
		temp = root
		while temp:
			lis.append(temp.data)
			bt = temp.bottom
			while bt:
				lis.append(bt.data)
				bt = bt.bottom
			temp = temp.next
		lis.sort()
		tempp = Node(0)
		thead = tempp
		for i in lis:
			temp = Node(i)
			print(temp.data, end=' ')
			tempp.next = temp
			tempp = tempp.next


class Solution:

	def flatten(self, root):
		if root.next is None:
			return root
		nextroot = self.flatten(root.next)
		root.next = None
		return self.merge(root, nextroot)

	def merge(self, cur1, cur2):
		head = Node(0)
		temp = head
		while cur1 is not None and cur2 is not None:
			if cur1.data < cur2.data:
				temp.bottom = cur1
				cur1 = cur1.bottom
			else:
				temp.bottom = cur2
				cur2 = cur2.bottom
			temp = temp.bottom
		if cur1 is None:
			temp.bottom = cur2
		else:
			temp.bottom = cur1
		return head.bottom


class Solution:

	def flatten(self, root):
		temp = root
		num = []
		while temp is not None:
			k = temp
			while k:
				num.append(k.data)
				k = k.bottom
			temp = temp.next
		num.sort()
		j = 0
		k = Node(0)
		temp = k
		for i in num:
			new_node = Node(i)
			k.bottom = new_node
			k = k.bottom
		return temp.bottom


def sortedMerge(head1, head2):
	if not head2:
		return head1
	tmp = temp = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				tmp = head1
			else:
				tmp.bottom = head1
				tmp = tmp.bottom
			head1 = head1.bottom
		else:
			if not tmp:
				temp = head2
				tmp = head2
			else:
				tmp.bottom = head2
				tmp = tmp.bottom
			head2 = head2.bottom
	while head1:
		tmp.bottom = head1
		tmp = tmp.bottom
		head1 = head1.bottom
	while head2:
		tmp.bottom = head2
		tmp = tmp.bottom
		head2 = head2.bottom
	return temp

class Solution:

	def flatten(self, root):
		temp = root
		root = root.next
		while root:
			temp = sortedMerge(temp, root)
			root = root.next
		return temp


class Solution:

	def flatten(self, root):
		import heapq
		Node.__lt__ = lambda this, o: this.data < o.data
		node = Node(-1)
		ans = node
		hp = []
		tmp = root
		while tmp:
			hp.append(tmp)
			tmp = tmp.next
		heapq.heapify(hp)
		while hp:
			tmp = heapq.heappop(hp)
			node.bottom = tmp
			node = tmp
			if tmp.bottom:
				heapq.heappush(hp, tmp.bottom)
		return ans.bottom


class Solution:

	def flatten(self, root):

		def merge(a, b):
			temp = Node(0)
			res = temp
			while a and b:
				if a.data < b.data:
					temp.bottom = a
					temp = temp.bottom
					a = a.bottom
				else:
					temp.bottom = b
					temp = temp.bottom
					b = b.bottom
			if a:
				temp.bottom = a
			else:
				temp.bottom = b
			return res.bottom

		def flat(root):
			if not root or not root.next:
				return root
			root.next = flat(root.next)
			root = merge(root, root.next)
			return root
		return flat(root)


class Solution:

	def merge(self, l1, l2):
		if not l1:
			return l2
		if not l2:
			return l1
		head = Node(-1)
		tmp = head
		while l1 != None and l2 != None:
			if l1.data <= l2.data:
				tmp.bottom = l1
				l1 = l1.bottom
			else:
				tmp.bottom = l2
				l2 = l2.bottom
			tmp = tmp.bottom
		if l1 != None:
			tmp.bottom = l1
		if l2 != None:
			tmp.bottom = l2
		return head.bottom

	def flatten(self, root):
		while root.next != None:
			a = root
			b = root.next
			c = root.next.next
			root = self.merge(a, b)
			root.next = c
		return root


from heapq import *

class Solution:

	def flatten(self, root):
		Node.__lt__ = lambda this, o: this.data < o.data
		pre = ans = Node(-1)
		H = []
		nd = root
		while nd:
			H.append(nd)
			nd = nd.next
		heapify(H)
		while H:
			nd = heappop(H)
			pre.bottom = nd
			pre = nd
			if nd.bottom:
				heappush(H, nd.bottom)
		return ans.bottom


class Solution:

	def flatten(self, root):
		l = []
		temp = root
		while temp:
			l.append(temp.data)
			curr = temp.bottom
			while curr:
				l.append(curr.data)
				curr = curr.bottom
			temp = temp.next
		l.sort()
		head = Node(l[0])
		temp = head
		for i in l[1:]:
			newnode = Node(i)
			temp.bottom = newnode
			temp = newnode
		return head


class Solution:

	def merge(self, left, right):
		ltemp = left
		rtemp = right
		dummy = Node(-1)
		temp = dummy
		while ltemp and rtemp:
			if ltemp.data <= rtemp.data:
				temp.bottom = ltemp
				ltemp.next = None
				ltemp = ltemp.bottom
			else:
				temp.bottom = rtemp
				rtemp.next = None
				rtemp = rtemp.bottom
			temp = temp.bottom
		if ltemp:
			temp.bottom = ltemp
		if rtemp:
			temp.bottom = rtemp
		return dummy.bottom

	def flatten(self, root):
		if root.next == None:
			return root
		curr = root
		while curr.next:
			left = curr
			right = curr.next
			nxt = right.next
			curr = self.merge(left, right)
			curr.next = nxt
		return curr


def merge(a, b):
	if a is None:
		return b
	if b is None:
		return a
	result = None
	if a.data <= b.data:
		result = a
		result.bottom = merge(a.bottom, b)
	else:
		result = b
		result.bottom = merge(a, b.bottom)
	return result

class Solution:

	def flatten(self, root):
		if root is None or root.next is None:
			return root
		root.next = self.flatten(root.next)
		root = merge(root, root.next)
		return root


class Solution:

	def merge2ll(self, head1, head2):
		hf = None
		ht = None
		while head1 != None and head2 != None:
			if hf == None:
				if head1.data < head2.data:
					hf = head1
					ht = head1
					head1 = head1.bottom
				else:
					ht = head2
					hf = head2
					head2 = head2.bottom
			elif head1.data < head2.data:
				ht.bottom = head1
				ht = ht.bottom
				head1 = head1.bottom
			else:
				ht.bottom = head2
				ht = ht.bottom
				head2 = head2.bottom
		if head1 != None:
			ht.bottom = head1
		if head2 != None:
			ht.bottom = head2
		return hf

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		return self.merge2ll(root, self.flatten(root.next))


class Solution:

	def flatten(self, root):
		head = root
		a = root
		while a:
			temp = a.next
			while a.bottom:
				a = a.bottom
			a.bottom = temp
			a = a.bottom
		v = []
		while head is not None:
			v.append(head.data)
			head = head.bottom
		v.sort()
		result = Node(-1)
		temp = result
		for i in range(len(v)):
			result.bottom = Node(v[i])
			result = result.bottom
		temp = temp.bottom
		return temp


class Solution:

	def flatten(self, root):
		start = Node(0)
		heads = []
		while root:
			heads.append(root)
			root = root.next
			heads[-1].next = None
		root = start
		while heads:
			mini = heads[0].data
			index = 0
			for (i, head) in enumerate(heads):
				if head.data < mini:
					mini = head.data
					index = i
			root.bottom = heads[index]
			heads.pop(index)
			root = root.bottom
			if root.next:
				heads.append(root.next)
				root.next = None
			if root.bottom:
				heads.append(root.bottom)
		return start.bottom


class Solution:

	def flatten(self, root):
		temp = root
		l = []
		while temp:
			k = temp
			while k:
				l.append(k.data)
				k = k.bottom
			temp = temp.next
		l.sort()

		class N:

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

		class LL:

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

			def ins(self, k):
				if self.head == None:
					self.head = N(k)
					self.tail = self.head
				else:
					self.tail.bottom = N(k)
					self.tail = self.tail.bottom
		q = LL()
		for x in l:
			q.ins(x)
		return q.head


class Solution:

	def flatten(self, root):

		def merge(head1, head2):
			cur1 = head1
			cur2 = head2
			ans = Node(123)
			a = ans
			while cur1 and cur2:
				if cur1.data < cur2.data:
					a.bottom = cur1
					cur1 = cur1.bottom
				else:
					a.bottom = cur2
					cur2 = cur2.bottom
				a = a.bottom
			if cur1:
				a.bottom = cur1
			else:
				a.bottom = cur2
			return ans.bottom

		def flatten(head):
			if not head or not head.next:
				return head
			cur1 = head
			cur2 = flatten(head.next)
			return merge(cur1, cur2)
		return flatten(root)


class Solution:

	def flatten(self, root):
		cur = root
		li = []
		while cur:
			curi = cur
			while curi:
				li.append(curi.data)
				curi = curi.bottom
			cur = cur.next
		li.sort()
		kk = Node(0)
		ans = kk
		for i in li:
			node = Node(i)
			kk.bottom = node
			kk = kk.bottom
		return ans.bottom


class Solution:

	def mergetwolists(self, a, b):
		dummy = Node(0)
		ans = dummy
		while a != None and b != None:
			if a.data < b.data:
				dummy.bottom = a
				dummy = dummy.bottom
				a = a.bottom
			else:
				dummy.bottom = b
				dummy = dummy.bottom
				b = b.bottom
			if a:
				dummy.bottom = a
			else:
				dummy.bottom = b
		return ans.bottom

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		root.next = self.flatten(root.next)
		root = self.mergetwolists(root, root.next)
		return root


def traverse(root, arr):
	if root is None:
		return
	arr.append(root.data)
	traverse(root.next, arr)
	traverse(root.bottom, arr)

class Solution:

	def flatten(self, root):
		arr = []
		traverse(root, arr)
		arr.sort()
		head = Node(arr[0])
		current = head
		for i in range(1, len(arr)):
			current.bottom = Node(arr[i])
			current = current.bottom
		return head


class Solution:

	def flatten(self, root):
		a = []
		roo = root
		k = m = Node(0)
		while roo:
			c = roo
			while c:
				a.append(c.data)
				c = c.bottom
			roo = roo.next
		a.sort()
		for h in a[:-1]:
			k.data = h
			k.next = None
			if k.bottom is None:
				k.bottom = Node(0)
			k = k.bottom
		k.data = a[-1]
		return m


class Solution:

	def flatten(self, root):
		head1 = root
		head2 = root.next
		while head2:
			prev = None
			curr1 = head1
			curr2 = head2
			while curr1 and curr2:
				if curr1.data <= curr2.data:
					prev = curr1
					curr1 = curr1.bottom
				elif prev is None:
					temp = curr2.bottom
					curr2.bottom = curr1
					prev = curr2
					root = curr2
					curr2 = temp
				else:
					temp = curr2.bottom
					prev.bottom = curr2
					curr2.bottom = curr1
					prev = curr2
					curr2 = temp
			if curr2 is not None:
				prev.bottom = curr2
			head1 = root
			head2 = head2.next
		return root


class Solution:

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		root.next = self.flatten(root.next)
		root = self.merge(root, root.next)
		return root

	def merge(self, root1, root2):
		new = Node(0)
		res = new
		while root1 and root2:
			if root1.data < root2.data:
				res.bottom = root1
				root1 = root1.bottom
			else:
				res.bottom = root2
				root2 = root2.bottom
			res = res.bottom
		if root1:
			res.bottom = root1
		if root2:
			res.bottom = root2
		return new.bottom


class Solution:

	def flatten(self, root):

		def f(root1, root2):
			temp = Node(0)
			res = temp
			while root1 and root2:
				if root1.data < root2.data:
					temp.bottom = root1
					root1 = root1.bottom
					temp = temp.bottom
				else:
					temp.bottom = root2
					root2 = root2.bottom
					temp = temp.bottom
			if root1:
				temp.bottom = root1
			else:
				temp.bottom = root2
			return res.bottom
		if not root or not root.next:
			return root
		root.next = self.flatten(root.next)
		return f(root, root.next)


class Solution:

	def flatten(self, root):
		x = []
		while root:
			x.append(root)
			root = root.next
		ans = []
		for i in x:
			ans.append(i.data)
			while i.bottom:
				i = i.bottom
				ans.append(i.data)
		for i in sorted(ans):
			print(i, end=' ')


class Solution:

	def append_node(self, root, next):
		if root is None:
			return next
		if next is None:
			return root
		if root.data < next.data:
			result = root
			result.bottom = self.append_node(root.bottom, next)
		else:
			result = next
			result.bottom = self.append_node(root, next.bottom)
		return result

	def flatten(self, root):
		if root == None:
			return root
		return self.append_node(root, self.flatten(root.next))


class Solution:

	def append_node(self, root):
		if root is not None:
			self.answer.append(root.data)
			if root.bottom is not None:
				self.append_node(root.bottom)
			if root.next is not None:
				self.append_node(root.next)

	def flatten(self, root):
		self.answer = list()
		self.append_node(root)
		self.answer.sort()
		for i in self.answer:
			print(i, end=' ')


class Solution:

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		root.next = self.flatten(root.next)
		root = self.merge(root, root.next)
		return root

	def merge(self, head1, head2):
		dummy = Node(0)
		temp = dummy
		while head1 and head2:
			if head1.data < head2.data:
				dummy.bottom = head1
				dummy = dummy.bottom
				head1 = head1.bottom
			else:
				dummy.bottom = head2
				dummy = dummy.bottom
				head2 = head2.bottom
		if head1 != None:
			dummy.bottom = head1
		else:
			dummy.bottom = head2
		return temp.bottom


class Solution:

	def merge_ll(self, a, b):
		if not a:
			return b
		if not b:
			return a
		res = ans = Node(-1)
		while a and b:
			if a.data < b.data:
				res.bottom = a
				a = a.bottom
				res = res.bottom
			else:
				res.bottom = b
				b = b.bottom
				res = res.bottom
		if a:
			res.bottom = a
		else:
			res.bottom = b
		return ans.bottom

	def flatten(self, root):
		if not root or not root.next:
			return root
		root.next = self.flatten(root.next)
		root = self.merge_ll(root, root.next)
		return root


class Solution:

	def flatten(self, root):

		def merge_sort(head1, head2):
			a = Node(0)
			temp = a
			while head1 and head2:
				if head1.data < head2.data:
					a.bottom = head1
					a = a.bottom
					head1 = head1.bottom
				else:
					a.bottom = head2
					a = a.bottom
					head2 = head2.bottom
			if head1:
				a.bottom = head1
			if head2:
				a.bottom = head2
			return temp.bottom
		if not root or not root.next:
			return root
		root.next = self.flatten(root.next)
		root = merge_sort(root, root.next)
		return root


class Solution:

	def flatten(self, root):

		def change(head, cur):
			start = head
			while head.bottom and head.bottom.data < cur.data:
				head = head.bottom
			temp1 = cur.bottom
			temp11 = cur.next
			temp2 = head.bottom
			head.bottom = cur
			cur.bottom = temp2
			if temp1:
				start.next = temp1
				temp1.next = temp11
			else:
				start.next = temp11
			return start.next
		ans = root
		cur = root.next
		while cur:
			if cur and cur.data < ans.data:
				ans.next = None
				temp1 = cur.bottom
				temp2 = cur.next
				cur.bottom = ans
				ans = cur
				if temp1:
					ans.next = temp1
					temp1.next = temp2
				else:
					ans.next = temp2
				cur = ans.next
			cur = change(ans, cur)
		return ans


def merge(x, y):
	if not x:
		return y
	if not y:
		return x
	res = None
	if x.data < y.data:
		res = x
		res.bottom = merge(x.bottom, y)
	else:
		res = y
		res.bottom = merge(x, y.bottom)
	return res

class Solution:

	def flatten(self, root):
		if not root or not root.next:
			return root
		root.next = self.flatten(root.next)
		root = merge(root, root.next)
		return root


class Solution:

	def flatten(self, root):
		arr = []
		while root:
			p = root
			while p:
				arr.append(p.data)
				p = p.bottom
			root = root.next
		arr.sort()
		new = head = Node('*')
		i = 0
		while i < len(arr):
			new.bottom = Node(arr[i])
			i += 1
			new = new.bottom
		return head.bottom


class Solution:

	def flatten(self, root):
		head = root
		while root.next:
			nxt = root.next
			while root.bottom:
				root = root.bottom
			root.bottom = nxt
			root = nxt
		return self.mergeSort(head)

	def mergeSort(self, head):
		if head.bottom == None:
			return head
		l = head
		mid = self.getMid(head)
		r = mid.bottom
		mid.bottom = None
		left = self.mergeSort(l)
		right = self.mergeSort(r)
		return self.merge(left, right)

	def getMid(self, head):
		(slow, fast) = (head, head.bottom)
		while fast and fast.bottom:
			slow = slow.bottom
			fast = fast.bottom.bottom
		return slow

	def merge(self, left, right):
		tail = dummy = Node(0)
		while left and right:
			if left.data < right.data:
				tail.bottom = left
				left = left.bottom
			else:
				tail.bottom = right
				right = right.bottom
			tail = tail.bottom
		if left:
			tail.bottom = left
		if right:
			tail.bottom = right
		return dummy.bottom


class Solution:

	def flatten(self, root):

		def recurmerge(root1, root2):
			if not root1:
				return root2
			if not root2:
				return root1
			if root1.data < root2.data:
				res = root1
				res.bottom = recurmerge(root1.bottom, root2)
			else:
				res = root2
				res.bottom = recurmerge(root1, root2.bottom)
			return res

		def merge(root1, root2):
			(node1, node2) = (root1, root2)
			finroot = Node(-1)
			finnode = finroot
			while node1 and node2:
				if node1.data < node2.data:
					finnode.bottom = node1
					node1 = node1.bottom
				else:
					finnode.bottom = node2
					node2 = node2.bottom
				finnode = finnode.bottom
			if node1:
				finnode.bottom = node1
			if node2:
				finnode.bottom = node2
			return finroot.bottom

		def flattened(root):
			if not root or not root.next:
				return root
			return recurmerge(root, flattened(root.next))
		return flattened(root)


class Solution:

	def flatten(self, root):
		p = root
		while p.next is not None:
			q = p
			while q.bottom is not None:
				q = q.bottom
			q.bottom = p.next
			p.next = p.next.next
		p = root
		q = root.bottom
		while p.bottom is not None:
			p.next = q
			p = p.bottom
			q = q.bottom
		p = root
		while p is not None:
			q = p.next
			max = p.data
			temp = None
			while q is not None:
				if max > q.data:
					max = q.data
					temp = q
				q = q.next
			if temp is not None:
				max = p.data
				p.data = temp.data
				temp.data = max
			p = p.next
		return root


class Solution:

	def flatten(self, root):
		if root and root.next:
			(left, slow, fast) = (root, root, root.next)
			while slow and fast and fast.next:
				slow = slow.next
				fast = fast.next.next
			right = slow.next
			slow.next = None
			return self.merge(self.flatten(left), self.flatten(right))
		return root

	def merge(self, a, b):
		if a and b:
			if a.data <= b.data:
				a.bottom = self.merge(a.bottom, b)
				return a
			else:
				b.bottom = self.merge(a, b.bottom)
				return b
		return a or b


a = int(input())
for i in range(a):
	c = int(input())
	b = list(map(int, input().split()))
	d = list(map(int, input().split()))
	d.sort()
	print(*d)


class Solution:

	def mergeSort(self, a, b):
		if not a:
			return b
		if not b:
			return a
		choice = None
		if a.data < b.data:
			choice = a
			choice.bottom = self.mergeSort(a.bottom, b)
		else:
			choice = b
			choice.bottom = self.mergeSort(a, b.bottom)
		choice.next = None
		return choice

	def flatten(self, root):
		if root is None or root.next is None:
			return root
		root.next = self.flatten(root.next)
		root = self.mergeSort(root, root.next)
		return root


class Solution:

	def flatten(self, root):
		b = []
		tmp = head
		a = head
		while tmp != None:
			b.append(tmp.data)
			if tmp.bottom == None:
				tmp.bottom = a.next
				a = a.next
			tmp = tmp.bottom
		b.sort()
		tmp = head
		for i in b:
			tmp.data = i
			tmp = tmp.bottom
		return head


class Solution:

	def flatten(self, root):
		new = d = Node(-1)
		v = x = Node(-1)
		l = []
		while root:
			k = p = root
			while k:
				new.bottom = k
				l.append(k.data)
				k = k.bottom
				new = new.bottom
			root = p.next
		l.sort()
		while l:
			v.bottom = Node(l.pop(0))
			v = v.bottom
		return x.bottom


from heapq import *

class Solution:

	def flatten(self, root):
		ctr = 0
		res = []
		tmp = head
		while tmp:
			ctr += 1
			heappush(res, (tmp.data, ctr, tmp))
			tmp = tmp.next
		dummy = Node(0)
		tmp = dummy
		while res:
			ctr += 1
			node = heappop(res)[2]
			tmp.bottom = node
			tmp = node
			if node.bottom:
				heappush(res, (node.bottom.data, ctr, node.bottom))
		return dummy.bottom


class Solution:

	def flatten(self, root):

		def sortedMerge(head1, head2):
			t1 = head1
			t2 = head2
			if head1.data < head2.data:
				head = head1
				head1 = head1.bottom
			else:
				head = head2
				head2 = head2.bottom
			t = head
			while head1 and head2:
				if head1.data < head2.data:
					t.bottom = head1
					head1 = head1.bottom
					t = t.bottom
				else:
					t.bottom = head2
					head2 = head2.bottom
					t = t.bottom
			if not head1:
				t.bottom = head2
			else:
				t.bottom = head1
			return head
		L = []
		while root is not None:
			L.append(root)
			root = root.next
		root = L.pop(0)
		while L:
			root = sortedMerge(root, L.pop(0))
		return root


class Solution:

	def sortedMerge(self, head1, head2):
		head = Node(-1)
		curr = head
		while head1 and head2:
			if head1.data <= head2.data:
				curr.bottom = head1
				head1 = head1.bottom
			else:
				curr.bottom = head2
				head2 = head2.bottom
			curr = curr.bottom
		if head1:
			curr.bottom = head1
		if head2:
			curr.bottom = head2
		return head.bottom

	def flatten(self, root):
		head = root
		nextNode = head.next
		while nextNode:
			head = self.sortedMerge(head, nextNode)
			nextNode = nextNode.next
		return head


class Solution:

	def flatten(self, root):

		def merge(l1, l2):
			head = Node(0)
			tmp = head
			while l1 and l2:
				if l1.data <= l2.data:
					tmp.bottom = l1
					l1 = l1.bottom
				else:
					tmp.bottom = l2
					l2 = l2.bottom
				tmp = tmp.bottom
			if l1:
				tmp.bottom = l1
			if l2:
				tmp.bottom = l2
			return head.bottom
		root1 = root.next
		while root1:
			tmp = root1
			root1 = root1.next
			tmp.next = None
			root = merge(root, tmp)
		return root


import heapq

class Solution:

	def createMinHeap(self, head, minHeap):
		counter = 0
		ptr = head
		while ptr:
			minHeap.append((ptr.data, counter, ptr))
			nextPtr = ptr.next
			ptr.next = None
			ptr = nextPtr
			counter += 1
		heapq.heapify(minHeap)
		return counter

	def flatten(self, root):
		minHeap = []
		counter = self.createMinHeap(root, minHeap)
		newHead = newTail = Node(None)
		while minHeap:
			(_, _, node) = heapq.heappop(minHeap)
			bottomNode = node.bottom
			newTail.bottom = node
			newTail = node
			node.bottom = None
			if bottomNode:
				heapq.heappush(minHeap, (bottomNode.data, counter, bottomNode))
				counter += 1
		return newHead.bottom


class Solution:

	def merge(self, root1, root2):
		dummy = Node(0)
		newnode = dummy
		while root1 and root2:
			if root1.data < root2.data:
				newnode.bottom = root1
				root1 = root1.bottom
			else:
				newnode.bottom = root2
				root2 = root2.bottom
			newnode = newnode.bottom
		if root1:
			newnode.bottom = root1
		if root2:
			newnode.bottom = root2
		return dummy.bottom

	def flatten(self, root):
		if not root:
			return None
		if not root.next:
			return root
		return self.merge(root, self.flatten(root.next))


class Solution:

	def mergeTwoLists(self, a, b):
		temp = Node(0)
		res = temp
		while a is not None and b is not None:
			if a.data < b.data:
				temp.bottom = a
				temp = temp.bottom
				a = a.bottom
			else:
				temp.bottom = b
				temp = temp.bottom
				b = b.bottom
		if a:
			temp.bottom = a
		else:
			temp.bottom = b
		return res.bottom

	def flatten(self, root):
		if root is None or root.next is None:
			return root
		root.next = self.flatten(root.next)
		root = self.mergeTwoLists(root, root.next)
		return root


class Solution:

	def flatten(self, root):

		def merge(l1, l2):
			dummy = head = Node(0)
			while l1 or l2:
				if l1 and l2:
					if l1.data < l2.data:
						head.bottom = l1
						l1 = l1.bottom
					else:
						head.bottom = l2
						l2 = l2.bottom
				elif l1:
					head.bottom = l1
					l1 = l1.bottom
				else:
					head.bottom = l2
					l2 = l2.bottom
				head = head.bottom
			return dummy.bottom
		head = None
		while root:
			(t, root) = (root, root.next)
			t.next = None
			head = merge(head, t)
		return head


class Solution:

	def flatten(self, root):
		btm = root
		temp = root
		lis = []
		while temp:
			while btm:
				lis.append(btm.data)
				btm = btm.bottom
			temp = temp.next
			btm = temp
		lis.sort()
		btm = root
		temp = root
		for i in range(len(lis)):
			if btm == None:
				temp.bottom = Node(lis[i])
				btm = temp.bottom.bottom
				temp = temp.bottom
			else:
				btm.data = lis[i]
				temp = btm
				btm = btm.bottom
		return root


class Solution:

	def flatten(self, root):
		ans = []
		t1 = root
		t2 = root
		while t1:
			while t2:
				ans.append(t2.data)
				t2 = t2.bottom
			t1 = t1.next
			t2 = t1
		ans.sort()
		temp = Node(ans[0])
		root = temp
		for j in range(1, len(ans)):
			temp.bottom = Node(ans[j])
			temp = temp.bottom
		return root


class Solution:

	def merge(self, a, b):
		if not a:
			return b
		if not b:
			return a
		head = Node(-1)
		temp = head
		while a != None and b != None:
			if a.data <= b.data:
				temp.bottom = a
				a = a.bottom
			else:
				temp.bottom = b
				b = b.bottom
			temp = temp.bottom
		if a != None:
			temp.bottom = a
		if b != None:
			temp.bottom = b
		return head.bottom

	def flatten(self, root):
		if root.next == None:
			return root
		root.next = self.flatten(root.next)
		root = self.merge(root, root.next)
		return root


class Solution:

	def flatten(self, root):
		arr = []
		if root:
			ptr = root
			ptr1 = None
			while ptr:
				arr.append(ptr.data)
				if ptr.bottom:
					ptr1 = ptr.bottom
				while ptr1:
					arr.append(ptr1.data)
					ptr1 = ptr1.bottom
				ptr = ptr.next
		arr.sort()
		dummy = Node(0)
		ptr = dummy
		for i in arr:
			node = Node(i)
			ptr.bottom = node
			ptr = ptr.bottom
		return dummy.bottom


class Solution:

	def merge(self, left, right):
		if not left:
			return right
		if not right:
			return left
		res = Node(-1)
		temp = res
		while left and right:
			if left.data <= right.data:
				temp.bottom = left
				left = left.bottom
			else:
				temp.bottom = right
				right = right.bottom
			temp = temp.bottom
		if left:
			temp.bottom = left
		else:
			temp.bottom = right
		return res.bottom

	def flatten(self, root):
		if root == None or root.next == None:
			return root
		root.next = self.flatten(root.next)
		root = self.merge(root, root.next)
		return root


class Solution:

	def flatten(self, root):
		nodes = set()
		cr = root
		while cr:
			nodes.add(cr)
			cr = cr.next
		ans = cur = Node(-1)
		while nodes:
			min_node = None
			for node in nodes:
				if not min_node or node.data < min_node.data:
					min_node = node
			cur.bottom = cur = Node(min_node.data)
			nodes.discard(min_node)
			if min_node.bottom:
				nodes.add(min_node.bottom)
		return ans.bottom


class Solution:

	def flatten(self, root):
		lst = []
		n = 0
		ptr = root
		while ptr:
			in_ptr = ptr
			while in_ptr:
				lst.append(in_ptr.data)
				n += 1
				in_ptr = in_ptr.bottom
			ptr = ptr.next
		lst.sort()
		root = None
		ptr = root
		i = 0
		for i in range(n):
			new_node = Node(lst[i])
			if root == None:
				root = new_node
				ptr = root
			else:
				ptr.bottom = Node(lst[i])
				ptr = ptr.bottom
		return root


class Solution:

	def sort(self, head):
		current = head
		index = None
		if head == None:
			return
		else:
			while current != None:
				index = current.next
				while index != None:
					if current.data > index.data:
						(current.bottom, index.bottom) = (index.bottom, current.bottom)
						temp = current.data
						current.data = index.data
						index.data = temp
					index = index.next
				current = current.next
		return head

	def flatten(self, root):
		if root is None or root.next is None:
			return root
		root = self.sort(root)
		curr = root
		while curr:
			if not curr.bottom:
				curr.bottom = curr.next
				curr.next = None
				curr = curr.next
			elif not curr.next:
				curr = curr.bottom
			elif curr.bottom.data <= curr.next.data:
				(curr.bottom.next, curr.next) = (curr.next, None)
				curr = curr.bottom
			else:
				tmp1 = curr.bottom
				(curr.bottom, curr.next) = (curr.next, None)
				curr = curr.bottom
				tmp2 = curr
				while tmp1:
					if not tmp2.bottom:
						tmp2.bottom = tmp1
						break
					if tmp2.bottom.data <= tmp1.data:
						tmp2 = tmp2.bottom
					else:
						tmp = tmp1
						tmp1 = tmp1.bottom
						tmp.bottom = tmp2.bottom
						tmp2.bottom = tmp
						tmp2 = tmp2.bottom
		return root


class Solution:

	def flatten(self, root):
		ntrace = root
		all_nodes = []
		while True:
			btrace = ntrace
			while True:
				if btrace is None:
					break
				all_nodes.append(btrace.data)
				btrace = btrace.bottom
			if ntrace is None:
				break
			ntrace = ntrace.next
		sorted_list = sorted(all_nodes)
		list_len = len(sorted_list)
		root = Node(sorted_list[0])
		tracer = 1
		head = None
		while tracer < list_len:
			node = Node(sorted_list[tracer])
			if head is None:
				head = root.bottom = node
			else:
				head.bottom = node
				head = node
			tracer += 1
		return root


class Solution:

	def merge(self, a, b):
		if not a and (not b):
			return None
		if not a:
			return b
		if not b:
			return a
		r = None
		if a.data < b.data:
			r = a
			r.bottom = self.merge(a.bottom, b)
		else:
			r = b
			r.bottom = self.merge(a, b.bottom)
		return r

	def flatten(self, root):
		if not root or not root.next:
			return root
		root.next = self.flatten(root.next)
		root = self.merge(root, root.next)
		return root


class Solution:

	def flatten(self, root):
		tmp = []
		while root:
			cur = root
			while cur:
				tmp.append(cur.data)
				cur = cur.bottom
			root = root.next
		tmp.sort()
		res = Node(0)
		cur = res
		for t in tmp:
			cur.bottom = Node(t)
			cur = cur.bottom
		return res.bottom


class Solution:

	def merge(self, x, y):
		if x is None:
			return y
		if y is None:
			return x
		if x.data < y.data:
			x.bottom = self.merge(x.bottom, y)
			return x
		y.bottom = self.merge(x, y.bottom)
		return y

	def flatten(self, root):
		if root is None:
			return root
		if root.next is None:
			return root
		root.next = self.flatten(root.next)
		return self.merge(root, root.next)


class Solution:

	def flatten(self, root):
		res = []
		headNode = root
		while True:
			res.append(headNode.data)
			node = headNode.bottom
			while node is not None:
				res.append(node.data)
				node = node.bottom
			if headNode.next is None:
				break
			headNode = headNode.next
		res.sort()
		prev = None
		for x in res[::-1]:
			temp = prev
			prev = Node(x)
			prev.bottom = temp
		return prev


class Solution:

	def flatten(self, root):
		while root.next:
			(curr, prev) = (root, None)
			while curr.next is not None:
				prev = curr
				curr = curr.next
			(cprev, pprev) = (prev, None)
			while curr:
				if cprev and cprev.data < curr.data:
					pprev = cprev
					cprev = cprev.bottom
				else:
					temp = curr
					curr = curr.bottom
					if pprev is None:
						pprev = cprev
						(pprev.data, temp.data) = (temp.data, pprev.data)
						temp.bottom = pprev.bottom
						pprev.bottom = temp
						cprev = temp
						continue
					temp.bottom = pprev.bottom
					pprev.bottom = temp
					pprev = temp
			prev.next = None
		return root


class Solution:

	def flatten_list(self, l1, l2):
		l1.next = None
		l2.next = None
		newhead = Node(0)
		newtail = newhead
		while l1 is not None and l2 is not None:
			if l1.data < l2.data:
				temp = l1
				l1 = l1.bottom
			else:
				temp = l2
				l2 = l2.bottom
			newtail.bottom = temp
			newtail = temp
			temp.next = temp.bottom = None
		if l1 is not None:
			while l1 is not None:
				temp = l1
				l1 = l1.bottom
				newtail.bottom = temp
				newtail = temp
				temp.next = temp.bottom = None
		if l2 is not None:
			while l2 is not None:
				temp = l2
				l2 = l2.bottom
				newtail.bottom = temp
				newtail = temp
				temp.next = temp.bottom = None
		temp = newhead
		newhead = newhead.bottom
		del temp
		return newhead

	def flatten(self, root):
		temp = root
		while temp is not None:
			l1 = temp
			l2 = temp.next
			if l2 is None:
				break
			temp = l2.next
			newhead = self.flatten_list(l1, l2)
			newhead.next = temp
			temp = newhead
		return temp


class Solution:

	def merge(self, root, nextroot):
		dummy = Node(-1)
		dummy.next = nextroot.next
		temp = dummy
		while root or nextroot:
			if root and nextroot and (root.data <= nextroot.data) or nextroot == None:
				temp.bottom = root
				root = root.bottom
			else:
				temp.bottom = nextroot
				nextroot = nextroot.bottom
			temp = temp.bottom
		dummy.bottom.next = dummy.next
		return dummy.bottom

	def flatten(self, root):
		if root == None:
			return root
		while root and root.next:
			root = self.merge(root, root.next)
		return root