Segment Linked List Partitioning

Given a singly linked list and an integer pivot, rearrange the list such that all nodes with values less than the pivot come before all nodes with values greater than or equal to the pivot. The relative order of the nodes in each partition must remain the same. More formally, for a linked list L and a pivot value P, partition L into two lists L₁ and L₂ where every node in L₁ satisfies (node.val < P) and every node in L₂ satisfies (node.val \ge P), then output the concatenation of L₁ followed by L₂.

inputFormat

Input is read from standard input (stdin). The first line contains space-separated integers representing the values of the linked list nodes. The second line contains a single integer representing the pivot value.

outputFormat

Output the modified linked list as a sequence of space-separated integers on one line, corresponding to the new order after partitioning.## sample

3 5 8 5 10 2 1
5

3 2 1 5 8 5 10