Relative Ordering Sort

You are given an array of integers. Your task is to sort the array such that all negative numbers appear before all non-negative numbers while preserving the relative order of the negative and non-negative numbers.

Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), let \(N = [a_i : a_i < 0]\) and \(P = [a_j : a_j \ge 0]\), both in the same order as in \(A\). The desired output is the concatenation \(N \Vert P\).

inputFormat

The input consists of a single line containing space-separated integers. If the input line is empty, the array is considered empty.

outputFormat

Output a single line containing the rearranged array as space-separated integers.

1 2 3 4

1 2 3 4