Partition Linked List

You are given a singly linked list and an integer \(x\). Your task is to partition the linked list such that all nodes with values less than \(x\) come first, followed by nodes whose values are equal to \(x\), and then nodes with values greater than \(x\). The relative order of the nodes in each of the three partitions should remain the same as in the original list.

Example:

Input:
6
1 4 3 2 5 2
3
Output:
1 2 2 3 4 5

</p>

Note: The input is read from standard input and the output should be written to standard output.

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) representing the number of nodes in the linked list.
• The second line contains \(n\) space-separated integers denoting the node values.
• The third line contains an integer \(x\) around which the partitioning is to be performed.

All input should be read from standard input (stdin).

outputFormat

Output the partitioned linked list as a sequence of integers separated by a single space in one line. The output should be written to standard output (stdout).

## sample

6
1 4 3 2 5 2
3

1 2 2 3 4 5