Given a linked list and a value x, partition it such that all nodes less than x come first, then all nodes with value equal to x and finally nodes with value greater than x. The original relative order of the nodes in each of the three partitions should be preserved. The partition must work in-place.
 
Example 1:
Input:
1->4->3->2->5->2->3,
x = 3
Output:
1->2->2->3->3->4->5
Explanation: 
Nodes with value less than 3 come first, 
then equal to 3 and then greater than 3.
Example 2:
Input:
1->4->2->10 
x = 3
Output: 
1->2->4->10
Explanation:
Nodes with value less than 3 come first,
then equal to 3 and then greater than 3.
Your task:
You don't need to read input or print anything. Your task is to complete the function partition() which takes the head of the inked list and an integer x as input, and returns the head of the modified linked list after arranging the values according to x.
 
Expected time complexity : O(n)
Expected Auxiliary Space: O(n)
 
Constraints:
1 <= N <= 10^{5}
1 <= k <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



"""



class Node:

    def __init__(self, data):

		self.data = data

		self.next = None



"""

class Solution:

    def partition(self, head, x):

        #code here

Solutions:
class Solution:

	def partition(self, head, x):
		less = []
		gre = []
		eq = []
		tmp = head
		while tmp:
			if tmp.data < x:
				less.append(tmp.data)
			elif tmp.data == x:
				eq.append(tmp.data)
			elif tmp.data > x:
				gre.append(tmp.data)
			tmp = tmp.next
		less = less + eq + gre
		head = None
		tmp = None
		for i in less:
			if head is None:
				node = Node(i)
				node.next = None
				head = node
				tmp = node
			else:
				node = Node(i)
				tmp.next = node
				tmp = node
		return head


class Solution:

	def partition(self, head, x):
		(a, b, c) = ([], [], [])
		cu = head
		while cu is not None:
			if cu.data < x:
				a.append(cu.data)
			elif cu.data == x:
				c.append(cu.data)
			else:
				b.append(cu.data)
			cu = cu.next
		y = a + c
		z = y + b
		z.append('$')
		(s, e) = (None, None)
		for i in z:
			if i != '$':
				if s is None:
					n = Node(i)
					s = n
					e = n
				else:
					n = Node(i)
					e.next = n
					e = n
		return s


class Solution:

	def partition(self, head, x):
		less = l = Node(0)
		equal = eq = Node(0)
		great = g = Node(0)
		ptr = head
		while ptr:
			if ptr.data < x:
				l.next = ptr
				ptr = ptr.next
				l = l.next
				l.next = None
			elif ptr.data == x:
				eq.next = ptr
				ptr = ptr.next
				eq = eq.next
				eq.next = None
			else:
				g.next = ptr
				ptr = ptr.next
				g = g.next
				g.next = None
		eq.next = great.next
		l.next = equal.next
		return less.next


class Solution:

	def partition(self, head, x):
		if head is None:
			return
		left = Node(0)
		right = Node(0)
		equal = Node(0)
		l = left
		r = right
		e = equal
		while head:
			if head.data < x:
				l.next = head
				l = l.next
			elif head.data > x:
				r.next = head
				r = r.next
			else:
				e.next = head
				e = e.next
			head = head.next
			l.next = equal.next
			e.next = right.next
			r.next = None
		return left.next


class Solution:

	def partition(self, head, x):
		itr = head
		a = []
		b = []
		c = []
		while itr:
			if itr.data < x:
				a.append(itr.data)
			if itr.data == x:
				b.append(itr.data)
			if itr.data > x:
				c.append(itr.data)
			itr = itr.next
		k = a + b
		z = k + c
		head1 = None
		tail = None
		for i in z:
			if head1 is None:
				newnode = Node(i)
				head1 = newnode
				tail = newnode
			else:
				newnode = Node(i)
				tail.next = newnode
				tail = newnode
		return head1


class Solution:

	def partition(self, head, x):
		temp = head
		lhead = None
		ghead = None
		ehead = None
		while temp:
			node = temp
			temp = temp.next
			node.next = None
			if node.data == x:
				if ehead == None:
					ehead = node
					tehead = ehead
				else:
					tehead.next = node
					tehead = tehead.next
			elif node.data > x:
				if ghead == None:
					ghead = node
					tghead = ghead
				else:
					tghead.next = node
					tghead = tghead.next
			elif lhead == None:
				lhead = node
				tlhead = lhead
			else:
				tlhead.next = node
				tlhead = tlhead.next
		if lhead != None:
			if ehead != None:
				tlhead.next = ehead
				if ghead != None:
					tehead.next = ghead
			elif ghead != None:
				tlhead.next = ghead
			return lhead
		else:
			if ehead != None:
				if ghead != None:
					tehead.next = ghead
				return ehead
			elif ghead != None:
				return ghead
			return head


class Solution:

	def partition(self, head, x):
		(dum_1, dum_2, dum_3) = (Node(-1), Node(-1), Node(-1))
		(d1, d2, d3) = (dum_1, dum_2, dum_3)
		node = head
		while node:
			if node.data < x:
				d1.next = node
				d1 = d1.next
			elif node.data == x:
				d2.next = node
				d2 = d2.next
			else:
				d3.next = node
				d3 = d3.next
			prev = node
			node = node.next
			prev.next = None
		if dum_1.next != None:
			ans = dum_1.next
			if dum_2.next != None:
				d1.next = dum_2.next
				d2.next = dum_3.next
			else:
				d1.next = dum_3.next
		elif dum_1.next == None:
			if dum_2.next != None:
				ans = dum_2.next
				d2.next = dum_3.next
			else:
				ans = dum_3.next
		return ans


class Solution:

	def partition(self, head, x):
		(smallerHead, smallerTail) = (None, None)
		(equalHead, equalTail) = (None, None)
		(greaterHead, greaterTail) = (None, None)
		while head is not None:
			if head.data < x:
				if smallerHead is None:
					smallerHead = head
					smallerTail = head
				else:
					smallerTail.next = head
					smallerTail = smallerTail.next
			elif head.data == x:
				if equalHead is None:
					equalHead = head
					equalTail = head
				else:
					equalTail.next = head
					equalTail = equalTail.next
			elif greaterHead is None:
				greaterHead = head
				greaterTail = head
			else:
				greaterTail.next = head
				greaterTail = greaterTail.next
			head = head.next
		if greaterTail is not None:
			greaterTail.next = None
		if smallerHead is None:
			if equalHead is None:
				return greaterHead
			equalTail.next = greaterHead
			return equalHead
		if equalHead is None:
			smallerTail.next = greaterHead
			return smallerHead
		smallerTail.next = equalHead
		equalTail.next = greaterHead
		return smallerHead


class Solution:

	def partition(self, head, x):
		node = head
		(new_head, curr) = (None, None)
		while node is not None:
			if node.data < x:
				if new_head is None:
					new_head = Node(node.data)
					curr = new_head
				else:
					curr.next = Node(node.data)
					curr = curr.next
			node = node.next
		node = head
		while node is not None:
			if node.data == x:
				if new_head is None:
					new_head = Node(node.data)
					curr = new_head
				else:
					curr.next = Node(node.data)
					curr = curr.next
			node = node.next
		node = head
		while node is not None:
			if node.data > x:
				if new_head is None:
					new_head = Node(node.data)
					curr = new_head
				else:
					curr.next = Node(node.data)
					curr = curr.next
			node = node.next
		return new_head


class Solution:

	def partition(self, head, x):
		le = None
		eq = None
		gr = None
		prev_le = None
		prev_eq = None
		prev_gr = None
		while head:
			if head.data == x:
				if not eq:
					eq = head
				else:
					prev_eq.next = head
				prev_eq = head
			elif head.data < x:
				if not le:
					le = head
				else:
					prev_le.next = head
				prev_le = head
			else:
				if not gr:
					gr = head
				else:
					prev_gr.next = head
				prev_gr = head
			head = head.next
		if le != None:
			head = le
			if eq != None:
				prev_le.next = eq
				if gr != None:
					prev_eq.next = gr
					prev_gr.next = None
				else:
					prev_eq.next = None
			elif gr != None:
				prev_le.next = gr
				prev_gr.next = None
			else:
				prev_le.next = None
		elif eq != None:
			head = eq
			if gr != None:
				prev_eq.next = gr
				prev_gr.next = None
			else:
				prev_eq.next = None
		else:
			head = gr
			if not head:
				prev_gr.next = None
		return head


class Node:

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

class Solution:

	def partition(self, head, x):
		less = Node(0)
		equal = Node(0)
		grea = Node(0)
		tmp1 = less
		tmp2 = equal
		tmp3 = grea
		while head:
			if head.data < x:
				less.next = head
				less = less.next
			elif head.data == x:
				equal.next = head
				equal = equal.next
			else:
				grea.next = head
				grea = grea.next
			head = head.next
		grea.next = None
		equal.next = tmp3.next
		less.next = tmp2.next
		return tmp1.next


class Solution:

	def partition(self, head, x):
		(left, mid, right) = (Node(0), Node(0), Node(0))
		(ltail, mtail, rtail) = (left, mid, right)
		while head:
			if head.data < x:
				ltail.next = head
				ltail = ltail.next
			elif head.data == x:
				mtail.next = head
				mtail = mtail.next
			else:
				rtail.next = head
				rtail = rtail.next
			head = head.next
		if mid.next:
			ltail.next = mid.next
			mtail.next = right.next
			rtail.next = None
		else:
			ltail.next = right.next
			rtail.next = None
		return left.next


class Solution:

	def partition(self, head, x):
		a = []
		b = []
		c = []
		temp = head
		while temp:
			if temp.data < x:
				a.append(temp.data)
			elif temp.data == x:
				b.append(temp.data)
			else:
				c.append(temp.data)
			temp = temp.next
		new = a + b + c
		start = None
		for elm in new:
			node = Node(elm)
			if start is None:
				start = node
			else:
				temp.next = node
			temp = node
		return start


class Solution:

	def partition(self, start, x):
		a = []
		b = []
		c = []
		count = 0
		temp = start
		while temp:
			if temp.data < x:
				a.append(temp.data)
			elif temp.data == x:
				b.append(temp.data)
			else:
				c.append(temp.data)
			temp = temp.next
		total = a + b + c
		newStart = Node(-1)
		temp = newStart
		for i in range(len(total)):
			node = Node(total[i])
			temp.next = node
			temp = node
		return newStart.next


class Solution:

	def partition(self, head, x):
		smaller = Node(-1)
		equal = Node(-1)
		larger = Node(-1)
		a = smaller
		b = equal
		c = larger
		temp = head
		while temp:
			nxt = temp.next
			if temp.data < x:
				a.next = temp
				a = a.next
				a.next = None
			elif temp.data == x:
				b.next = temp
				b = b.next
				b.next = None
			else:
				c.next = temp
				c = c.next
				c.next = None
			temp = nxt
		if smaller.next != None:
			if equal.next != None:
				a.next = equal.next
				b.next = larger.next
				return smaller.next
			else:
				a.next = larger.next
				return smaller.next
		elif equal.next != None:
			b.next = larger.next
			return equal.next
		else:
			return larger.next


class Solution:

	def partition(self, head, x):
		g = []
		m = []
		s = []
		r = []
		t1 = head
		t2 = head
		while t1:
			if t1.data > x:
				g.append(t1.data)
				t1 = t1.next
			elif t1.data == x:
				m.append(t1.data)
				t1 = t1.next
			else:
				s.append(t1.data)
				t1 = t1.next
		r = s + m + g
		for i in r:
			t2.data = i
			t2 = t2.next
		return head


class Solution:

	def partition(self, head, x):
		small = []
		big = []
		num = []
		res = []
		temp1 = head
		temp2 = head
		while temp1:
			if temp1.data > x:
				big.append(temp1.data)
			elif temp1.data == x:
				num.append(temp1.data)
			else:
				small.append(temp1.data)
			temp1 = temp1.next
		res = small + num + big
		for i in res:
			temp2.data = i
			temp2 = temp2.next
		return head


class Solution:

	def partition(self, head, x):
		a = head
		arr = []
		while a:
			if a.data < x:
				arr.append(a.data)
			a = a.next
		a = head
		while a:
			if a.data == x:
				arr.append(a.data)
			a = a.next
		a = head
		while a:
			if a.data > x:
				arr.append(a.data)
			a = a.next
		a = head
		for i in arr:
			a.data = i
			a = a.next
		return head


class Solution:

	def partition(self, head, x):
		big = list()
		small = list()
		temp = head
		count = 0
		while temp:
			if temp.data < x:
				small.append(temp.data)
			elif temp.data > x:
				big.append(temp.data)
			else:
				count += 1
			temp = temp.next
		temp = head
		while small:
			temp.data = small.pop(0)
			temp = temp.next
		while count:
			temp.data = x
			count -= 1
			temp = temp.next
		while big:
			temp.data = big.pop(0)
			temp = temp.next
		return head


class Solution:

	def partition(self, head, x):
		smaller = []
		item = []
		bigger = []
		tek = head
		while tek != None:
			if tek.data == x:
				item.append(tek.data)
			elif tek.data < x:
				smaller.append(tek.data)
			elif tek.data > x:
				bigger.append(tek.data)
			tek = tek.next
		head1 = Node(0)
		tek1 = head1
		i = 0
		while i < len(smaller):
			tek1.next = Node(smaller[i])
			tek1 = tek1.next
			i += 1
		i = 0
		while i < len(item):
			tek1.next = Node(item[i])
			tek1 = tek1.next
			i += 1
		i = 0
		while i < len(bigger):
			tek1.next = Node(bigger[i])
			tek1 = tek1.next
			i += 1
		return head1.next


class Solution:

	def partition(self, head, x):
		smaller = []
		item = []
		bigger = []
		while head:
			if head.data < x:
				smaller.append(head)
			elif head.data == x:
				item.append(head)
			else:
				bigger.append(head)
			head = head.next
		smaller += item + bigger
		start = smaller[0]
		head = start
		for item in smaller[1:]:
			head.next = item
			head = item
		head.next = None
		return start


class Solution:

	def partition(self, head, x):
		before_x = before_x_head = Node(0)
		equal_x = equal_x_head = Node(0)
		after_x = after_x_head = Node(0)
		while head:
			if head.data < x:
				before_x.next = head
				before_x = before_x.next
			elif head.data == x:
				equal_x.next = head
				equal_x = equal_x.next
			else:
				after_x.next = head
				after_x = after_x.next
			head = head.next
		after_x.next = None
		equal_x.next = after_x_head.next
		before_x.next = equal_x_head.next
		return before_x_head.next


class Solution:

	def partition(self, head, x):
		dummy1 = head1 = Node(-1)
		dummy2 = head2 = Node(-1)
		dummy3 = head3 = Node(-1)
		while head:
			if head.data > x:
				head1.next = head
				head1 = head1.next
			elif head.data == x:
				head3.next = head
				head3 = head3.next
			else:
				head2.next = head
				head2 = head2.next
			head = head.next
		head1.next = None
		if dummy2.next == None:
			if dummy3.next == None:
				return dummy1.next
			head3.next = dummy1.next
			return dummy3.next
		if dummy3.next == None:
			head2.next = dummy1.next
			return dummy2.next
		head2.next = dummy3.next
		head3.next = dummy1.next
		return dummy2.next


class Solution:

	def partition(self, head, x):
		b = []
		a = []
		c = []
		tmp = head
		while tmp != None:
			if tmp.data < x:
				a.append(tmp.data)
			if tmp.data == x:
				c.append(tmp.data)
			if tmp.data > x:
				b.append(tmp.data)
			tmp = tmp.next
		a = a + c + b
		tmp = head
		for i in a:
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

	def partition(self, head, x):
		pre = None
		pos = None
		npos = None
		nhead = None
		nhead2 = None
		h1 = h2 = head
		nhead3 = None
		while h1:
			if h1.data < x:
				if not pre:
					nhead = h1
					pre = h1
				else:
					pre.next = h1
					pre = h1
			elif h1.data == x:
				if not pos:
					pos = h1
					nhead2 = h1
				else:
					pos.next = h1
					pos = h1
			elif h1.data > x:
				if not npos:
					npos = h1
					nhead3 = h1
				else:
					npos.next = h1
					npos = h1
			h1 = h1.next
			if pos and pos.next:
				pos.next = None
			if pre and pre.next:
				pre.next = None
			if npos and npos.next:
				npos.next = None
		if nhead:
			pre.next = nhead2
			if nhead2:
				pos.next = nhead3
			else:
				pre.next = nhead3
			return nhead
		elif not nhead:
			if nhead2:
				pos.next = nhead3
				return nhead2
			else:
				return nhead3


class Solution:

	def partition(self, head, x):
		a = []
		b = []
		c = []
		curr = head
		while curr is not None:
			if curr.data < x:
				a.append(curr.data)
			if curr.data == x:
				c.append(curr.data)
			if curr.data > x:
				b.append(curr.data)
			curr = curr.next
		k = a + c
		z = k + b
		z.append('x')
		head2 = None
		tail = None
		for ele in z:
			if ele != 'x':
				if head2 is None:
					newnode = Node(ele)
					head2 = newnode
					tail = newnode
				else:
					newnode = Node(ele)
					tail.next = newnode
					tail = newnode
		return head2


class Solution:

	def partition(self, head, x):
		less = []
		eq = []
		gr = []
		t = head
		while t:
			d = t.data
			if d < x:
				less.append(d)
			elif d == x:
				eq.append(d)
			else:
				gr.append(d)
			t = t.next
		(i, j, k) = (0, 0, 0)
		t = head
		while i < len(less):
			t.data = less[i]
			i += 1
			t = t.next
		while j < len(eq):
			t.data = eq[j]
			j += 1
			t = t.next
		while k < len(gr):
			t.data = gr[k]
			k += 1
			t = t.next
		return head


class Solution:

	def partition(self, head, x):
		a = Node(-1)
		b = Node(-1)
		c = Node(-1)
		ans1 = a
		ans2 = b
		ans3 = c
		while head:
			if head.data < x:
				a.next = Node(head.data)
				a = a.next
			elif head.data > x:
				c.next = Node(head.data)
				c = c.next
			else:
				b.next = Node(head.data)
				b = b.next
			head = head.next
		b.next = ans3.next
		a.next = ans2.next
		return ans1.next


class Solution:

	def partition(self, head, x):
		left = Node(-1)
		left_tail = left
		right = Node(-1)
		right_tail = right
		equal = Node(-1)
		equal_tail = equal
		while head:
			if head.data > x:
				right_tail.next = Node(head.data)
				right_tail = right_tail.next
			elif head.data < x:
				left_tail.next = Node(head.data)
				left_tail = left_tail.next
			else:
				equal_tail.next = Node(head.data)
				equal_tail = equal_tail.next
			head = head.next
		equal_tail.next = right.next
		left_tail.next = equal.next
		right_tail.next = None
		return left.next


class Solution:

	def partition(self, head, x):
		if not head:
			return None
		(less, equal, greater) = (Node(0), Node(0), Node(0))
		(l, e, g) = (less, equal, greater)
		while head:
			if head.data < x:
				l.next = head
				l = l.next
			elif head.data == x:
				e.next = head
				e = e.next
			else:
				g.next = head
				g = g.next
			(head, l.next, e.next, g.next) = (head.next, equal.next, greater.next, None)
		return less.next


class Solution:

	def partition(self, head, x):
		curr = small = Node(0)
		dummy = big = Node(0)
		xxx = equ = Node(0)
		itr = head
		while itr:
			if itr.data < x:
				small.next = itr
				itr = itr.next
				small = small.next
				small.next = None
			elif itr.data == x:
				equ.next = itr
				itr = itr.next
				equ = equ.next
				equ.next = None
			else:
				big.next = itr
				itr = itr.next
				big = big.next
				big.next = None
		res = ans = Node(0)
		itr = curr.next
		while itr:
			ans.next = itr
			itr = itr.next
			ans = ans.next
			ans.next = None
		itr = xxx.next
		while itr:
			ans.next = itr
			itr = itr.next
			ans = ans.next
			ans.next = None
		itr = dummy.next
		while itr:
			ans.next = itr
			itr = itr.next
			ans = ans.next
			ans.next = None
		return res.next


class Solution:

	def partition(self, head, x):
		small = Node(0)
		s = small
		large = Node(0)
		l = large
		equal = Node(0)
		e = equal
		temp = head
		while temp != None:
			if temp.data < x:
				s.next = temp
				s = s.next
			elif temp.data == x:
				e.next = temp
				e = e.next
			elif temp.data > x:
				l.next = temp
				l = l.next
			temp = temp.next
		e.next = None
		l.next = None
		if equal.next != None:
			s.next = equal.next
			e.next = large.next
		else:
			s.next = large.next
		return small.next


class Solution:

	def partition(self, head, x):
		dummy1 = Node(-1)
		dummy2 = Node(-1)
		dummy3 = Node(-1)
		less = dummy1
		equal = dummy2
		grater = dummy3
		curr = head
		while curr:
			if curr.data < x:
				less.next = curr
				less = less.next
			elif curr.data == x:
				equal.next = curr
				equal = equal.next
			elif curr.data > x:
				grater.next = curr
				grater = grater.next
			curr = curr.next
		if dummy2.next:
			less.next = dummy2.next
			equal.next = dummy3.next
			grater.next = None
		else:
			less.next = dummy3.next
			grater.next = None
		return dummy1.next


class Solution:

	def partition(self, head, x):
		sH = None
		sL = None
		gL = None
		gH = None
		eH = None
		eL = None
		while head != None:
			if head.data == x:
				if eH == None:
					eH = eL = head
				else:
					eL.next = head
					eL = eL.next
			elif head.data < x:
				if sH == None:
					sL = sH = head
				else:
					sL.next = head
					sL = head
			elif gH == None:
				gL = gH = head
			else:
				gL.next = head
				gL = head
			head = head.next
		if gL != None:
			gL.next = None
		if sH == None:
			if eH == None:
				return gH
			eL.next = gH
			return eH
		if eH == None:
			sL.next = gH
			return sH
		sL.next = eH
		eL.next = gH
		return sH


class Solution:

	def partition(self, head, x):
		if not head or not head.next:
			return head
		less = Node(0)
		equal = Node(0)
		greater = Node(0)
		less_nd = less
		equal_nd = equal
		greater_nd = greater
		current = head
		while current:
			if current.data < x:
				less_nd.next = current
				less_nd = current
			elif current.data == x:
				equal_nd.next = current
				equal_nd = current
			else:
				greater_nd.next = current
				greater_nd = current
			current = current.next
		less_nd.next = equal.next if equal.next else greater.next
		equal_nd.next = greater.next
		greater_nd.next = None
		head = less.next
		return head


class Solution:

	def add(self, nd, sm, sm_n):
		if not sm:
			sm = nd
		elif sm_n:
			sm_n.next = nd
			sm_n = sm_n.next
		else:
			sm_n = nd
			sm.next = sm_n
		return (sm, sm_n)

	def pp(self, nd):
		while nd:
			print(nd.data, end=' ')
			nd = nd.next
		print()

	def ch(self, eq, lg, eq_n, lg_n):
		if not eq:
			if lg:
				eq = lg
				eq_n = lg_n
				(lg, lg_n) = (None, None)
		return (eq, lg, eq_n, lg_n)

	def partition(self, head, x):
		sm = None
		lg = None
		eq = None
		sm_n = None
		lg_n = None
		eq_n = None
		while head != None:
			if head.data < x:
				(sm, sm_n) = self.add(head, sm, sm_n)
			elif head.data > x:
				(lg, lg_n) = self.add(head, lg, lg_n)
			else:
				(eq, eq_n) = self.add(head, eq, eq_n)
			head = head.next
		if sm_n:
			sm_n.next = None
		if eq_n:
			eq_n.next = None
		if lg_n:
			lg_n.next = None
		ans = None
		(eq, lg, eq_n, lg_n) = self.ch(eq, lg, eq_n, lg_n)
		(sm, eq, sm_n, eq_n) = self.ch(sm, eq, sm_n, eq_n)
		(eq, lg, eq_n, lg_n) = self.ch(eq, lg, eq_n, lg_n)
		if not sm_n:
			sm_n = sm
			if sm_n:
				sm_n.next = None
		if not eq_n:
			eq_n = eq
			if eq_n:
				eq_n.next = None
		if not lg_n:
			lg_n = lg
			if lg_n:
				lg_n.next = None
		ans = sm
		if eq:
			sm_n.next = eq
			sm_n = eq_n
		if lg:
			sm_n.next = lg
			sm_n = lg_n
		return ans


class Solution:

	def partition(self, head, x):
		(K, L, M, N) = ([], [], [], [])
		while head:
			i = head.data
			if i < x:
				L.append(i)
			elif i == x:
				M.append(i)
			else:
				N.append(i)
			head = head.next
		L.extend(M)
		L.extend(N)
		L.reverse()
		L1 = LinkedList()
		for i in L:
			L1.push(i)
		return L1.head


class Solution:

	def partition(self, head, x):
		less = []
		equal = []
		greater = []
		p = head
		while p:
			if p.data < x:
				less.append(p.data)
			elif p.data == x:
				equal.append(p.data)
			else:
				greater.append(p.data)
			p = p.next
		p = head
		i = 0
		t = less + equal + greater
		n = len(t)
		while p and i < n:
			p.data = t[i]
			p = p.next
			i += 1
		return head


class Solution:

	def partition(self, head, x):
		left = Node(None)
		mid = Node(None)
		right = Node(None)
		lTail = left
		mTail = mid
		rTail = right
		while head:
			if head.data < x:
				lTail.next = head
				lTail = lTail.next
			elif head.data == x:
				mTail.next = head
				mTail = mTail.next
			else:
				rTail.next = head
				rTail = rTail.next
			head = head.next
		rTail.next = None
		mTail.next = right.next
		lTail.next = mid.next
		return left.next


class Solution:

	def partition(self, head, x):
		low = None
		loa = low
		eq = None
		eqa = eq
		high = None
		hia = high
		tmp = head
		while tmp:
			if tmp.data < x:
				if not low:
					low = Node(tmp.data)
					loa = low
				else:
					low.next = Node(tmp.data)
					low = low.next
			elif tmp.data == x:
				if not eq:
					eq = Node(tmp.data)
					eqa = eq
				else:
					eq.next = Node(tmp.data)
					eq = eq.next
			elif not high:
				high = Node(tmp.data)
				hia = high
			else:
				high.next = Node(tmp.data)
				high = high.next
			tmp = tmp.next
		if low:
			if eq:
				if high:
					low.next = eqa
					eq.next = hia
				else:
					low.next = eqa
			elif high:
				low.next = hia
			return loa
		elif eq:
			if high:
				eq.next = hia
			return eqa
		else:
			return hia


class Solution:

	def partition(self, head, x):
		dummy1 = Node(-1)
		dummy2 = Node(-1)
		dummy3 = Node(-1)
		(curr1, curr2, curr3) = (dummy1, dummy2, dummy3)
		while head:
			if head.data < x:
				dummy1.next = head
				dummy1 = dummy1.next
			elif head.data == x:
				dummy2.next = head
				dummy2 = dummy2.next
			else:
				dummy3.next = head
				dummy3 = dummy3.next
			head = head.next
		dummy2.next = curr3.next
		dummy1.next = curr2.next
		dummy3.next = None
		return curr1.next


class Solution:

	def partition(self, head, x):
		(h1, h2, h3) = (Node(-1), Node(-1), Node(-1))
		(t1, t2, t3) = (h1, h2, h3)
		while head:
			if head.data < x:
				t1.next = Node(head.data)
				t1 = t1.next
			elif head.data == x:
				t2.next = Node(head.data)
				t2 = t2.next
			else:
				head.data > x
				t3.next = Node(head.data)
				t3 = t3.next
			head = head.next
		if h2.next == None:
			t1.next = h3.next
			return h1.next
		else:
			t1.next = h2.next
			t2.next = h3.next
			return h1.next


class Solution:

	def partition(self, head, x):
		less = Node(-1)
		eq = Node(-2)
		great = Node(-3)
		(h1, h2, h3) = (less, eq, great)
		(t1, t2, t3) = (h1, h2, h3)
		temp = head
		while temp:
			if temp.data < x:
				t1.next = Node(temp.data)
				t1 = t1.next
			elif temp.data == x:
				t2.next = Node(temp.data)
				t2 = t2.next
			else:
				t3.next = Node(temp.data)
				t3 = t3.next
			temp = temp.next
		if h2.next:
			t1.next = h2.next
		else:
			t1.next = h3.next
		t2.next = h3.next
		return h1.next


class Solution:

	def partition(self, head, x):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		a = []
		b = []
		c = []
		for i in l:
			if i < x:
				a.append(i)
			elif i == x:
				b.append(i)
			else:
				c.append(i)
		for i in a + b + c:
			print(i, end=' ')


class Solution:

	def partition(self, head, x):
		a = []
		cur = head
		while cur is not None:
			a.append(cur.data)
			cur = cur.next
		b = a.copy()
		c = 0
		j = 0
		for i in range(len(b)):
			if b[i] < x:
				a[j] = b[i]
				c += 1
				j += 1
		l = j
		for k in range(len(b)):
			if b[k] == x:
				a[l] = b[k]
				c += 1
				l += 1
		g = l
		for z in range(len(b)):
			if b[z] > x:
				a[g] = b[z]
				c += 1
				g += 1
		for i in a:
			print(i, end=' ')


class Solution:

	def partition(self, head, x):
		llist1 = llist2 = llist3 = None
		temp = head
		head1 = head2 = head3 = None
		if head == None or head.next == None:
			return head
		while temp:
			if temp.data < x:
				if llist1 == None:
					llist1 = Node(temp.data)
					head1 = llist1
				else:
					llist1.next = Node(temp.data)
					llist1 = llist1.next
			if temp.data == x:
				if llist2 == None:
					llist2 = Node(temp.data)
					head2 = llist2
				else:
					llist2.next = Node(temp.data)
					llist2 = llist2.next
			if temp.data > x:
				if llist3 == None:
					llist3 = Node(temp.data)
					head3 = llist3
				else:
					llist3.next = Node(temp.data)
					llist3 = llist3.next
			temp = temp.next
		if llist1 != None and llist2 == None and (llist3 == None):
			return head1
		if llist1 == None and llist2 != None and (llist3 == None):
			return head2
		if llist1 == None and llist2 == None and (llist3 != None):
			return head3
		if llist1 == None and llist2 != None and (llist3 != None):
			llist2.next = head3
			return head2
		if llist1 != None and llist2 != None and (llist3 == None):
			llist1.next = head2
			return head1
		if llist1 != None and llist2 == None and (llist3 != None):
			llist1.next = head3
			return head1
		if llist1 != None and llist2 != None and (llist3 != None):
			llist1.next = head2
			llist2.next = head3
			return head1


class Solution:

	def partition(self, head, x):
		lsl = []
		lse = []
		lsa = []
		temp = head
		while temp:
			if temp.data < x:
				lsl.append(temp.data)
			elif temp.data == x:
				lse.append(temp.data)
			else:
				lsa.append(temp.data)
			temp = temp.next
		ls = lsl + lse + lsa
		temp2 = head
		i = 0
		while temp2:
			temp2.data = ls[i]
			i += 1
			temp2 = temp2.next
		return head


class Solution:

	def partition(self, head, x):
		if head == None:
			return
		left = Node(0)
		right = Node(0)
		mid = Node(0)
		l1 = left
		l2 = right
		l3 = mid
		while head:
			if head.data < x:
				l1.next = head
				l1 = l1.next
			elif head.data > x:
				l2.next = head
				l2 = l2.next
			else:
				l3.next = head
				l3 = l3.next
			head = head.next
			l1.next = mid.next
			l3.next = right.next
			l2.next = None
		return left.next


class Solution:

	def partition(self, head, x):
		temp1 = head
		t1 = Node(0)
		n1 = t1
		t2 = Node(0)
		n2 = t2
		t3 = Node(0)
		n3 = t3
		while temp1:
			if temp1.data < x:
				n = Node(temp1.data)
				t1.next = n
				t1 = n
			elif temp1.data == x:
				n = Node(temp1.data)
				t2.next = n
				t2 = n
			else:
				n = Node(temp1.data)
				t3.next = n
				t3 = n
			temp1 = temp1.next
		if n2.next is None:
			t1.next = n3.next
		else:
			t1.next = n2.next
			t2.next = n3.next
		return n1.next


class Solution:

	def partition(self, head, x):
		left = Node(0)
		mid = Node(0)
		right = Node(0)
		s1 = left
		s2 = mid
		s3 = right
		curNode = head
		while curNode:
			nextNode = curNode.next
			if curNode.data < x:
				left.next = curNode
				left = left.next
			elif curNode.data > x:
				right.next = curNode
				right = right.next
			else:
				mid.next = curNode
				mid = mid.next
			curNode.next = None
			curNode = nextNode
		if s2.next == None:
			if s1.next != None:
				left.next = s3.next
				return s1.next
			else:
				return s3.next
		elif s1.next == None:
			mid.next = s3.next
			return s2.next
		else:
			left.next = s2.next
			mid.next = s3.next
			return s1.next


class Solution:

	def partition(self, head, x):
		smallerHead = Node(-1)
		smallerEnd = smallerHead
		greaterHead = Node(-1)
		greaterEnd = greaterHead
		equalHead = Node(-1)
		equalEnd = equalHead
		curr = head
		while curr:
			if curr.data < x:
				smallerEnd.next = curr
				smallerEnd = smallerEnd.next
			elif curr.data > x:
				greaterEnd.next = curr
				greaterEnd = greaterEnd.next
			else:
				equalEnd.next = curr
				equalEnd = equalEnd.next
			curr = curr.next
		smallerEnd.next = equalHead.next if equalHead.next else greaterHead.next
		equalEnd.next = greaterHead.next
		greaterEnd.next = None
		return smallerHead.next


class Solution:

	def partition(self, head, x):
		if head is None or head.next is None:
			return head
		curr = head
		smaller = Node(-1)
		sp = smaller
		larger = Node(-1)
		lp = larger
		pivot = Node(-1)
		pp = pivot
		while curr != None:
			if curr.data == x:
				pp.next = curr
				pp = pp.next
			elif curr.data < x:
				sp.next = curr
				sp = sp.next
			else:
				lp.next = curr
				lp = lp.next
			curr = curr.next
		if smaller != None and pivot.next != None:
			sp.next = pivot.next
			pp.next = larger.next
			lp.next = None
		else:
			sp.next = larger.next
			lp.next = None
		return smaller.next


class Solution:

	def partition(self, head, x):
		d1 = Node(-1)
		d2 = Node(-1)
		d3 = Node(-1)
		low = d1
		mid = d2
		high = d3
		curr = head
		while curr:
			if curr.data < x:
				low.next = curr
				low = low.next
			elif curr.data == x:
				mid.next = curr
				mid = mid.next
			else:
				high.next = curr
				high = high.next
			curr = curr.next
		low.next = None
		mid.next = None
		high.next = None
		d1 = d1.next
		d2 = d2.next
		d3 = d3.next
		new = Node(-1)
		newhead = new
		if d1:
			new.next = d1
			new = low
		if d2:
			new.next = d2
			new = mid
		if d3:
			new.next = d3
		return newhead.next


class Solution:

	def partition(self, head, x):
		(s, small) = (None, None)
		(m, medium) = (None, None)
		(l, large) = (None, None)
		curr = head
		while curr:
			if curr.data < x:
				if not s:
					s = curr
					small = curr
				else:
					small.next = curr
					small = small.next
			elif curr.data == x:
				if not m:
					m = curr
					medium = curr
				else:
					medium.next = curr
					medium = medium.next
			elif not l:
				l = curr
				large = curr
			else:
				large.next = curr
				large = large.next
			curr = curr.next
		if s and m and l:
			small.next = m
			medium.next = l
			large.next = None
			return s
		elif s and m:
			small.next = m
			medium.next = None
			return s
		elif s and l:
			small.next = l
			large.next = None
			return s
		elif m and l:
			medium.next = l
			large.next = None
			return m
		elif s:
			return s
		elif m:
			return m
		else:
			return l


class Solution:

	def partition(self, head, x):
		smallerHead = None
		smallerLast = None
		greaterLast = None
		greaterHead = None
		equalHead = None
		equalLast = None
		while head != None:
			if head.data == x:
				if equalHead == None:
					equalHead = equalLast = head
				else:
					equalLast.next = head
					equalLast = equalLast.next
			elif head.data < x:
				if smallerHead == None:
					smallerLast = smallerHead = head
				else:
					smallerLast.next = head
					smallerLast = head
			elif greaterHead == None:
				greaterLast = greaterHead = head
			else:
				greaterLast.next = head
				greaterLast = head
			head = head.next
		if greaterLast != None:
			greaterLast.next = None
		if smallerHead == None:
			if equalHead == None:
				return greaterHead
			equalLast.next = greaterHead
			return equalHead
		if equalHead == None:
			smallerLast.next = greaterHead
			return smallerHead
		smallerLast.next = equalHead
		equalLast.next = greaterHead
		return smallerHead


class Solution:

	def partition(self, head, x):
		leftHead = Node(0)
		leftLast = leftHead
		rightHead = Node(0)
		rightLast = rightHead
		equalHead = Node(0)
		equalLast = equalHead
		while head != None:
			if head.data == x:
				equalLast.next = head
				equalLast = equalLast.next
			elif head.data < x:
				leftLast.next = head
				leftLast = head
			else:
				rightLast.next = head
				rightLast = head
			head = head.next
		if rightLast != None:
			rightLast.next = None
		if leftHead.next == None:
			if equalHead.next == None:
				return rightHead.next
			equalLast.next = rightHead.next
			return equalHead.next
		if equalHead.next == None:
			leftLast.next = rightHead.next
			return leftHead.next
		leftLast.next = equalHead.next
		equalLast.next = rightHead.next
		return leftHead.next


class Solution:

	def partition(self, head, x):
		before = beforeHead = Node(0)
		on = onHead = Node(0)
		afterHead = after = Node(0)
		while head:
			if head.data < x:
				before.next = head
				before = before.next
			elif head.data == x:
				on.next = head
				on = on.next
			else:
				after.next = head
				after = after.next
			head = head.next
		before.next = None
		after.next = None
		on.next = None
		onHead = onHead.next
		while onHead:
			before.next = onHead
			onHead = onHead.next
			before = before.next
		afterHead = afterHead.next
		while afterHead:
			before.next = afterHead
			before = before.next
			afterHead = afterHead.next
		return beforeHead.next


class Solution:

	def partition(self, head, x):
		(l, e, m) = (Node('dmy'), Node('dmy'), Node('dmy'))
		d = {'less': l, 'equal': e, 'more': m}
		n = head
		while True:
			v = n.data
			k = ['less', 'equal', 'more'][(v >= x) + (v > x)]
			d[k].next = n
			d[k] = n
			if not n.next:
				break
			n = n.next
		for k in d:
			d[k].next = None
		for (h, k) in ((m, 'equal'), (e, 'less')):
			if h.next:
				d[k].next = h.next
		return l.next


class Solution:

	def partition(self, head, x):
		(l, e, m) = (Node('dmy'), Node('dmy'), Node('dmy'))
		d = {'less': l, 'equal': e, 'more': m}
		n = head
		while True:
			v = n.data
			k = 'equal'
			if v < x:
				k = 'less'
			if v > x:
				k = 'more'
			d[k].next = n
			d[k] = n
			if not n.next:
				break
			n = n.next
		for k in d:
			d[k].next = None
		if m.next:
			d['equal'].next = m.next
		if e.next:
			d['less'].next = e.next
		return l.next
		s = [True if x.next else False for x in (l, e, m)]
		if s[2]:
			d['equal'].next = m.next
		if s[1] or s[2]:
			d['less'].next = e.next
		return l.next


class Solution:

	def partition(self, head, x):
		smaller_head = None
		smaller_last = None
		equal_head = None
		equal_last = None
		larger_head = None
		larger_last = None
		while head != None:
			if head.data == x:
				if equal_head == None:
					equal_head = head
					equal_last = head
				else:
					equal_last.next = head
					equal_last = equal_last.next
			elif head.data < x:
				if smaller_head == None:
					smaller_head = head
					smaller_last = head
				else:
					smaller_last.next = head
					smaller_last = smaller_last.next
			elif head.data > x:
				if larger_head == None:
					larger_head = head
					larger_last = head
				else:
					larger_last.next = head
					larger_last = larger_last.next
			head = head.next
		if larger_last != None:
			larger_last.next = None
		if smaller_head == None:
			if equal_head == None:
				return larger_head
			equal_last.next = larger_head
			return equal_head
		if equal_head == None:
			smaller_last.next = larger_head
			return smaller_head
		smaller_last.next = equal_head
		equal_last.next = larger_head
		return smaller_head


class Solution:

	def partition(self, head, x):
		sh = None
		sl = None
		eh = None
		el = None
		gh = None
		gl = None
		while head != None:
			if head.data == x:
				if eh == None:
					eh = head
					el = head
				else:
					el.next = head
					el = el.next
			elif head.data < x:
				if sh == None:
					sh = head
					sl = head
				else:
					sl.next = head
					sl = sl.next
			elif gh == None:
				gh = head
				gl = head
			else:
				gl.next = head
				gl = gl.next
			head = head.next
		if gl != None:
			gl.next = None
		if sh == None:
			if eh == None:
				return gh
			el.next = gh
			return eh
		if sh != None:
			if eh == None:
				sl.next = gh
				return sh
		sl.next = eh
		el.next = gh
		return sh


class Solution:

	def partition(self, head, x):
		res = []
		while head:
			res.append(head.data)
			head = head.next
		(l, s, r) = ([], [], [])
		for i in res:
			if i < x:
				l.append(i)
			elif i > x:
				r.append(i)
			else:
				s.append(i)
		ans = l + s + r
		temp1 = Node(0)
		temp = temp1
		for i in range(len(ans)):
			temp1.data = ans[i]
			if i == len(ans) - 1:
				break
			temp1.next = Node(0)
			temp1 = temp1.next
		return temp


class Solution:

	def partition(self, head, x):
		if head is None:
			return head
		less = Node(None)
		more = Node(None)
		equal = Node(None)
		l1 = less
		m1 = more
		e1 = equal
		temp = head
		while temp:
			if temp.data < x:
				if less.data == None:
					less.data = temp.data
				else:
					less.next = Node(temp.data)
					less = less.next
			elif temp.data == x:
				if equal.data == None:
					equal.data = temp.data
				else:
					equal.next = Node(temp.data)
					equal = equal.next
			elif more.data == None:
				more.data = temp.data
			else:
				more.next = Node(temp.data)
				more = more.next
			temp = temp.next
		less.next = None
		more.next = None
		equal.next = None
		while l1 and l1.data == None:
			l1 = l1.next
		while e1 and e1.data == None:
			e1 = e1.next
		while m1 and m1.data == None:
			m1 = m1.next
		if l1 == None:
			if e1 == None:
				return m1
			else:
				if m1 is None:
					return e1
				equal.next = m1
				return e1
		if m1 == None:
			if e1 is None:
				return l1
			else:
				less.next = e1
				return l1
		if e1 == None:
			less.next = m1
			return l1
		less.next = e1
		equal.next = m1
		return l1


class Solution:

	def partition(self, head, x):
		a = []
		temp1 = head
		while temp1 != None:
			a.append(temp1.data)
			temp1 = temp1.next
		m = []
		n = []
		o = []
		for i in a:
			if i < x:
				m.append(i)
			elif i == x:
				n.append(i)
			elif i > x:
				o.append(i)
		final = m + n + o
		temp2 = head
		i = 0
		while temp2 != None:
			temp2.data = final[i]
			i += 1
			temp2 = temp2.next
		return head


class Solution:

	def partition(self, head, x):
		start = head
		less = Node(None)
		equal = Node(None)
		more = Node(None)
		a1 = less
		a2 = more
		a3 = equal
		while start != None:
			if start.data < x:
				if a1.data is None:
					a1.data = start.data
				else:
					a1.next = Node(start.data)
					a1 = a1.next
			elif start.data == x:
				if a3.data == None:
					a3.data = start.data
				else:
					a3.next = Node(start.data)
					a3 = a3.next
			elif start.data > x:
				if a2.data is None:
					a2.data = start.data
				else:
					a2.next = Node(start.data)
					a2 = a2.next
			start = start.next
		a1.next = None
		a2.next = None
		a3.next = None
		a1.next = equal
		a3.next = more
		while less.data == None:
			less = less.next
		z1 = less
		while z1 and z1.next != None:
			if z1.next.data == None:
				z1.next = z1.next.next
			else:
				z1 = z1.next
		return less


class Solution:

	def insert(self, Head, Tail, Node):
		if Head is None:
			Head = Node
			Tail = Node
		else:
			Tail.next = Node
			Tail = Tail.next
		return (Head, Tail)

	def connectList(self, ListOneHead, ListOneTail, ListTwoHead, ListTwoTail):
		(head, tail) = (None, None)
		if ListOneHead and ListTwoHead:
			head = ListOneHead
			ListOneTail.next = ListTwoHead
			tail = ListTwoTail
		elif ListOneHead:
			head = ListOneHead
			tail = ListOneTail
		elif ListTwoHead:
			head = ListTwoHead
			tail = ListTwoTail
		return (head, tail)

	def partition(self, head, x):
		sHead = None
		sTail = None
		mHead = None
		mTail = None
		gHead = None
		gTail = None
		curr = head
		while curr:
			if curr.data < x:
				(sHead, sTail) = self.insert(sHead, sTail, curr)
			elif curr.data == x:
				(mHead, mTail) = self.insert(mHead, mTail, curr)
			else:
				(gHead, gTail) = self.insert(gHead, gTail, curr)
			curr = curr.next
		(tHead, tTail) = self.connectList(sHead, sTail, mHead, mTail)
		(head, tail) = self.connectList(tHead, tTail, gHead, gTail)
		tail.next = None
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = input()
		values = list(map(int, input().split()))
		for i in reversed(values):
			llist.push(i)
		k = int(input())
		new_head = LinkedList()
		ob = Solution()
		new_head = ob.partition(llist.head, k)
		llist.head = new_head
		llist.printList()
		t -= 1


class Solution:

	def partition(self, head, x):
		l = []
		m = []
		n = []
		t = head
		while t is not None:
			if t.data < x:
				l.append(t.data)
			elif t.data > x:
				n.append(t.data)
			else:
				m.append(t.data)
			t = t.next
		l.extend(m)
		l.extend(n)
		head = Node(l[0])
		temp = head
		for i in range(1, len(l)):
			new = Node(l[i])
			temp.next = new
			temp = new
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = input()
		values = list(map(int, input().split()))
		for i in reversed(values):
			llist.push(i)
		k = int(input())
		new_head = LinkedList()
		ob = Solution()
		new_head = ob.partition(llist.head, k)
		llist.head = new_head
		llist.printList()
		t -= 1


class Solution:

	def partition(self, head, x):
		l = Node(0)
		e = Node(0)
		r = Node(0)
		l1 = l
		e1 = e
		r1 = r
		while head:
			if head.data < x:
				l.next = head
				l = l.next
			elif head.data == x:
				e.next = head
				e = e.next
			else:
				r.next = head
				r = r.next
			head = head.next
		r.next = None
		e.next = r1.next
		l.next = e1.next
		return l1.next

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = input()
		values = list(map(int, input().split()))
		for i in reversed(values):
			llist.push(i)
		k = int(input())
		new_head = LinkedList()
		ob = Solution()
		new_head = ob.partition(llist.head, k)
		llist.head = new_head
		llist.printList()
		t -= 1


class Solution:

	def partition(self, head, x):
		left = Node(-99999)
		right = Node(-9999)
		eq = Node(-9999)
		r = right
		l = left
		q = eq
		while head:
			tmp = head.data
			nde = Node(tmp)
			if tmp < x:
				left.next = nde
				left = nde
			elif tmp == x:
				eq.next = nde
				eq = nde
			else:
				right.next = nde
				right = nde
			head = head.next
		if q.next:
			left.next = q.next
			eq.next = r.next
			return l.next
		left.next = r.next
		return l.next

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = input()
		values = list(map(int, input().split()))
		for i in reversed(values):
			llist.push(i)
		k = int(input())
		new_head = LinkedList()
		ob = Solution()
		new_head = ob.partition(llist.head, k)
		llist.head = new_head
		llist.printList()
		t -= 1


class Solution:

	def partition(self, head, x):
		if not head:
			return None
		left = l = Node(-1)
		equal = e = Node(-1)
		right = r = Node(-1)
		itr = head
		while itr:
			if itr.data < x:
				l.next = itr
				l = l.next
			elif itr.data > x:
				r.next = itr
				r = r.next
			else:
				e.next = itr
				e = e.next
			itr = itr.next
		if equal.next:
			l.next = equal.next
			e.next = right.next
			r.next = None
		else:
			l.next = right.next
			r.next = None
		return left.next