Alternate Positive and Negative Numbers

Given an array arr that contains an equal number of positive and negative elements, rearrange the given array such that positive and negative numbers are arranged alternatively. The respective relative order of positive and negative should be maintained.

Input:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ single space-separated integers representing the elements of the array.

Output:

For each test case, print a single line containing ‘N’ single space-separated integers such that positive and negative numbers are arranged alternatively.

Output of each test case will be printed on a separate line.

Example:

Input: 
 arr[ ] = { -1, 3, 5, 0, -2, -5 } 

Output: 
 arr[ ] = {3, -1, 5, -2, 0, -5 } (valid rearrangement)

Invalid: 
 arr[ ] = {3, -1, 0, -2, 5, -5 } (order changed) 

Invalid: 
 arr[ ] = {3, -1, 5, 0, -2, -5 } (not alternative)

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 5 * 103
• -109 ≤ arr[i] ≤ 109

Note:

Make changes in the same array, and no return or printing is needed. Consider zero (0) as a positive element. It is guaranteed that an answer always exists.