Rearrange Array by Negativity

Given an array of integers, rearrange the array such that all negative numbers appear before all non-negative numbers. The relative order among the negative numbers and among the non-negative numbers must be preserved.

In other words, if the original array is (a = [a_1, a_2, \dots, a_n]), then after rearrangement, all (a_i < 0) will come first (in the same order as they appeared originally), followed by all (a_i \ge 0) (also in their original order).

inputFormat

The input is provided via standard input (stdin) as a single line of space-separated integers. It may be empty or contain one or more integers. For example:

3 -4 2 -1 5 0 -6

outputFormat

Output the rearranged array as a single line of space-separated integers to standard output (stdout). For example, for the input above, the output should be:

-4 -1 -6 3 2 5 0## sample

3 -4 2 -1 5 0 -6

-4 -1 -6 3 2 5 0