Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

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

Example 2:

Input:
2 1
2
Output: 1 2

Constraints:

• The number of nodes in the list is in the range [0, 200]
• -100 ≤ Node.val ≤ 100
• -200 ≤ x ≤ 200

Input format: First line: space-separated integers. Second line: x.

Output format: Partitioned list.