Given an array of integers, print all the pairs having positive and negative values of a number that exists in the array.
NOTE: If no such pair exists, simply return an empty array, also multiple pairs of the same number could exist and you need to print each of them separately.
Example 1:
Input:
n = 8
a [ ] = {1, -3, 2, 3, 6, -1, -3, 3}
Output:
-1 1 -3 3 -3 3
Explanation:
The array contains both 1 and -1, and
3 & -3 two times.
 
Example 2:
Input:
n = 8
a [ ] = {4, 8, 9, -4, 1, -1, -8, -9}
Output:
-1 1 -4 4 -8 8 -9 9
Explanation:
Here, the array contains the pairs 1 & -1,
4 & -4, 8 & -8, and 9 & -9.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function PosNegPair() which takes the array a[] and its size n as inputs and returns all the required pairs in the increasing order of their absolute numbers.
 
Expected Time Complexity: O(nLog(n))
Expected Auxiliary Space: O(n)
 
Constraints:
1<=n<=10^{5}
-10^{5}<=a[i]<=10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(nLog(n))
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:

    def PosNegPair(self, a, n):

        #Code here

    

    

    

    

Solutions:
class Solution:

	def PosNegPair(self, arr, n):
		arr = list(map(int, arr))
		pos = {}
		neg = []
		for i in arr:
			if i > 0:
				if i in pos:
					pos[i] += 1
				else:
					pos[i] = 1
			else:
				neg.append(i)
		res = []
		neg.sort()
		for i in range(len(neg) - 1, -1, -1):
			k = abs(neg[i])
			if k in pos and pos[k] > 0:
				res.append(neg[i])
				res.append(-1 * neg[i])
				pos[k] -= 1
		return res
0


class Solution:

	def PosNegPair(self, a, n):
		d = dict()
		for i in range(len(a)):
			if int(a[i]) in d.keys():
				d[int(a[i])] += 1
			else:
				d[int(a[i])] = 1
		l = []
		y = list(d.keys())
		y.sort()
		for u in y:
			if u < 0 and abs(u) in d.keys():
				if d[u] == d[abs(u)]:
					l += (abs(u), u) * d[u]
				else:
					l += (abs(u), u) * min(d[u], d[abs(u)])
		l.reverse()
		return l
		return [1, 2, 3]


class Solution:

	def PosNegPair(self, a, n):
		pos = dict()
		neg = dict()
		for i in range(0, n):
			num = int(a[i])
			if num > 0:
				if num in pos:
					pos[num] += 1
				else:
					pos[num] = 1
			elif num in neg:
				neg[num] += 1
			else:
				neg[num] = 1
		a.clear()
		posval = sorted(pos)
		for key in posval:
			negKey = key * -1
			while negKey in neg and neg[negKey] != 0 and (pos[key] != 0):
				a.append(negKey)
				a.append(key)
				neg[negKey] -= 1
				pos[key] -= 1
		return a


from collections import defaultdict

class Solution:

	def PosNegPair(self, a, n):
		store = defaultdict(lambda : 0)
		pairs = []
		for item in a:
			item = int(item)
			if store[-item] > 0:
				num = abs(item)
				pairs.append([-num, num])
				store[-item] -= 1
			else:
				store[item] += 1
		output = []
		pairs.sort(reverse=True)
		for pair in pairs:
			output += pair
		return output


class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		freq = {}
		for i in a:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		res = []
		s = set()
		a.sort(reverse=True)
		for i in a:
			if i < 0:
				temp = 0
				if i not in s and -i in freq:
					temp = min(freq[i], freq[-i])
					s.add(i)
				temparr = [i, -i] * temp
				res.extend(temparr)
		return res


class Solution:

	def PosNegPair(self, a, n):
		pos_dict = dict()
		neg_dict = dict()
		for i in range(0, n):
			num = int(a[i])
			if num > 0:
				if num in pos_dict.keys():
					pos_dict[num] += 1
				else:
					pos_dict[num] = 1
			elif num in neg_dict.keys():
				neg_dict[num] += 1
			else:
				neg_dict[num] = 1
		ans = []
		for key in sorted(pos_dict.keys()):
			if key * -1 in neg_dict.keys():
				tmp = min(pos_dict[key], neg_dict[key * -1])
				for i in range(0, tmp):
					ans.append(str(key * -1))
					ans.append(str(key))
		return ans


class Solution:

	def PosNegPair(self, a, n):
		d = {}
		f = {}
		k = {}
		j = set()
		for i in a:
			if int(i) > 0:
				k[i] = 0
				j.add(int(i))
		for i in a:
			if i[0] == '-':
				if i[1:] in k:
					k[i[1:]] = i
		for i in a:
			if int(i) < 0:
				if i in f:
					f[i] += 1
				else:
					f[i] = 1
			elif i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for i in sorted(j):
			i = str(i)
			if i in k:
				t = k[i]
				if t in f:
					p = [t, i] * min(d[i], f[t])
					l += p
		return l


import collections

class Solution:

	def PosNegPair(self, a, n):
		a = [int(i) for i in a]
		x = []
		y = {}
		for i in a:
			if i in y:
				y[i] += 1
			else:
				y[i] = 1
		for i in y:
			if i > 0 and -1 * i in y:
				for j in range(min(y[i], y[-1 * i])):
					x.append([-1 * i, i])
		x.sort(key=lambda x: x[1])
		ans = []
		for i in x:
			ans.append(i[0])
			ans.append(i[1])
		return ans


class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		p = dict()
		n = []
		ans = []
		for ele in a:
			if ele > 0:
				if ele in p:
					p[ele] += 1
				else:
					p[ele] = 1
			else:
				n.append(ele)
		n.sort(reverse=True)
		for ele in n:
			if abs(ele) in p and p[abs(ele)] > 0:
				ans.extend([ele, abs(ele)])
				p[abs(ele)] -= 1
		return ans


class Solution:

	def PosNegPair(self, arr, n):
		arr = list(map(int, arr))
		arr.sort()
		dict1 = dict()
		dict2 = dict()
		list1 = []
		for i in arr:
			if i < 0:
				if i not in dict1:
					dict1[i] = 1
				else:
					dict1[i] += 1
			elif i > 0:
				if i not in dict2:
					dict2[i] = 1
					if -i in dict1:
						if dict2[i] <= dict1[-i]:
							list1.extend([-i, i])
				else:
					dict2[i] += 1
					if -i in dict1:
						if dict2[i] <= dict1[-i]:
							list1.extend([-i, i])
		if list1 == []:
			return []
		else:
			return list1


class Solution:

	def PosNegPair(self, a, n):
		arr = list(map(int, a))
		k = {}
		l = []
		for i in range(n):
			if arr[i] > 0:
				if arr[i] in k:
					k[arr[i]] += 1
				else:
					k[arr[i]] = 1
			else:
				l.append(arr[i])
		r = []
		l.sort()
		for i in range(len(l) - 1, -1, -1):
			j = abs(l[i])
			if j in k:
				if k[j] > 0:
					k[j] -= 1
					r.append(l[i])
					r.append(abs(l[i]))
		return r


class Solution:

	def PosNegPair(self, a, n):
		neg = []
		pos = []
		l = []
		for i in range(n):
			if int(a[i]) < 0:
				neg.append(int(a[i]))
			else:
				pos.append(int(a[i]))
		neg.sort(reverse=True)
		pos.sort()
		i = 0
		j = 0
		while i < len(neg) and len(pos) > 0:
			if abs(int(neg[i])) == int(pos[j]):
				l.append(neg[i])
				l.append(pos[j])
				j += 1
				i += 1
			elif abs(int(neg[i])) < int(pos[j]):
				i += 1
			else:
				j += 1
			if j == len(pos):
				break
		return l


from collections import Counter

class Solution:

	def PosNegPair(self, a, n):
		result = []
		negatives = []
		positives = []
		for number in a:
			if int(number) < 0:
				negatives.append(int(number))
			else:
				positives.append(int(number))
		posCount = dict(Counter(positives))
		for number in negatives:
			if abs(number) in posCount:
				numCount = posCount.get(abs(number))
				if numCount >= 1:
					result.append(number)
					result.append(abs(number))
					posCount[abs(number)] = numCount - 1
		return sorted(result, key=lambda number: abs(number))


class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		a.sort()
		dict1 = {}
		dict2 = {}
		result = []
		for i in a:
			if i < 0:
				if i not in dict1:
					dict1[i] = 1
				else:
					dict1[i] += 1
			elif i > 0:
				if i not in dict2:
					dict2[i] = 1
					if -i in dict1:
						if dict2[i] <= dict1[-i]:
							result.extend([-i, i])
				else:
					dict2[i] += 1
					if -i in dict1:
						if dict2[i] <= dict1[-i]:
							result.extend([-i, i])
		if len(result) == 0:
			return []
		else:
			return result


class Solution:

	def PosNegPair(self, a, n):
		m = {}
		ans = []
		neg = []
		a = list(map(int, a))
		for i in a:
			if i > 0:
				if i not in m:
					m[i] = 1
				else:
					m[i] += 1
			else:
				neg.append(i)
		neg.sort(reverse=True)
		for i in neg:
			if abs(i) in m and m[abs(i)] > 0:
				ans.append(i)
				ans.append(abs(i))
				m[abs(i)] -= 1
		return ans


class Solution:

	def PosNegPair(self, a, n):
		dic = {}
		for i in a:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		li = []
		for i in dic:
			if str(-int(i)) in dic:
				while dic[i] != 0 and dic[str(-int(i))] != 0:
					li.append(abs(int(i)))
					dic[i] -= 1
					dic[str(-int(i))] -= 1
		li.sort()
		ans = []
		for k in range(len(li)):
			ans.append('-' + str(li[k]))
			ans.append(str(li[k]))
		return ans


class Solution:

	def PosNegPair(self, arr, n):
		arr = list(map(int, arr))
		arr.sort()
		temp = []
		i = 0
		j = n - 1
		while i < j and arr[i] < 0 and (arr[j] > 0):
			if abs(arr[i]) > abs(arr[j]):
				i += 1
			elif abs(arr[i]) < abs(arr[j]):
				j -= 1
			else:
				temp.append(abs(arr[i]))
				i += 1
				j -= 1
		temp.sort()
		res = []
		for i in temp:
			res.append(-i)
			res.append(i)
		return res


class Solution:

	def PosNegPair(self, a, n):
		pos_dict = {}
		negArr = []
		for i in range(len(a)):
			key = int(a[i])
			if key > 0 and key in pos_dict:
				pos_dict[key] = pos_dict.get(key) + 1
			elif key > 0 and key not in pos_dict:
				pos_dict[key] = 1
			else:
				negArr.append(key)
		negArr.sort()
		result = []
		for i in range(len(negArr) - 1, -1, -1):
			key = abs(negArr[i])
			if key in pos_dict and pos_dict[key] > 0:
				result.append(negArr[i])
				result.append(key)
				pos_dict[key] = pos_dict.get(key) - 1
		return result


class Solution:

	def PosNegPair(self, a, n):
		m = {}
		for i in a:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		l = []
		for i in m:
			if i > 0:
				if -i in m:
					c = min(m[i], m[-i])
					b = [i] * c
					l.extend(b)
		l.sort()
		b = []
		for i in l:
			b.append(-i)
			b.append(i)
		return b


class Solution:

	def PosNegPair(self, a, n):
		ans = []
		a = list(map(int, a))
		a.sort(reverse=True)
		i = 0
		while i < n and a[i] >= 0:
			i += 1
		if i == n:
			return ans
		a = a[i:] + a[:i]
		left = 0
		right = n - 1
		while left < right:
			temp_sum = a[left] + a[right]
			if temp_sum == 0:
				ans.append(a[left])
				ans.append(a[right])
				left += 1
				right -= 1
			elif temp_sum < 0:
				right -= 1
			else:
				left += 1
		return ans


class Solution:

	def PosNegPair(self, a, n):
		ls = []
		k = {}
		for x in a:
			if x not in k.keys():
				k[x] = 1
			else:
				k[x] += 1
		for x in k.keys():
			if int(x) > 0:
				if str(int(x) * -1) in k.keys():
					m = min(k[x], k[str(int(x) * -1)])
					r = [int(x) * -1, int(x)] * m
					rv = [int(x)] + r
					ls.append(rv)
		sorted_list = sorted(ls, key=lambda x: x[0])
		res = []
		for x in sorted_list:
			res += x[1:]
		return res


class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		from collections import Counter
		freq = dict(Counter(a))
		all_keys = sorted(list(freq.keys()))
		ans = []
		for i in all_keys:
			if i < 0 and freq.get(-i) != None:
				ans += [-i, i] * min(freq[i], freq[-i])
		return ans[::-1]


class Solution:

	def PosNegPair(self, a, n):
		res = []
		a = list(map(int, a))
		pos = {}
		neg = {}
		for x in a:
			if x < 0:
				if x not in neg:
					neg[x] = 1
				else:
					neg[x] += 1
			elif x not in pos:
				pos[x] = 1
			else:
				pos[x] += 1
		for p in pos.keys():
			if -p in neg.keys():
				for _ in range(min(neg[-p], pos[p])):
					res.append(-p)
					res.append(p)
		return sorted(res, key=lambda x: abs(x))


class Solution:

	def PosNegPair(self, a, n):
		pos = {}
		neg = {}
		for i in a:
			i = int(i)
			if i > 0:
				if i in pos:
					pos[i] += 1
				else:
					pos[i] = 1
			else:
				i = abs(i)
				if i in neg:
					neg[i] += 1
				else:
					neg[i] = 1
		x = []
		for i in pos:
			if i in neg:
				y = min(pos[i], neg[i])
				for j in range(y):
					x.append(i)
		x.sort()
		ans = []
		for i in x:
			ans.append(-i)
			ans.append(i)
		return ans

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [x for x in input().strip().split()]
		ans = Solution().PosNegPair(a, n)
		if len(ans) == 0:
			print(0)
		else:
			print(*ans)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def PosNegPair(self, a, n):
		d = {}
		r = []
		k = []
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if i < 0 and -i in d:
				r.extend([-i, i] * min(d[i], d[-i]))
		r = sorted(r)
		for i in r:
			if i < 0:
				k.append(-i)
				k.append(i)
			else:
				break
		return k[::-1]

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ans = Solution().PosNegPair(a, n)
		if len(ans) == 0:
			print(0)
		else:
			print(*ans)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def PosNegPair(self, a, n):
		out = []
		a = list(map(int, a))
		a.sort()
		Hash1 = dict()
		Hash2 = dict()
		for i in a:
			if i < 0:
				if i not in Hash1:
					Hash1[i] = 1
				else:
					Hash1[i] += 1
			if i >= 0:
				if i not in Hash2:
					Hash2[i] = 1
					if -i in Hash1 and Hash2[i] <= Hash1[-i]:
						out.extend([-i, i])
				else:
					Hash2[i] += 1
					if -i in Hash1 and Hash2[i] <= Hash1[-i]:
						out.extend([-i, i])
		return out


class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		a.sort()
		i = 0
		j = n - 1
		li = []
		while i <= j:
			if int(a[i]) >= 0 or int(a[j]) <= 0:
				break
			if abs(a[i]) != abs(a[j]):
				if abs(a[j]) > abs(a[i]):
					j -= 1
				else:
					i += 1
			else:
				li.append(a[i])
				li.append(a[j])
				i += 1
				j -= 1
		for i in range(len(li)):
			li[i] = -1 * li[i]
		li.reverse()
		return li


class Solution:

	def PosNegPair(self, a, n):
		pos_dict = dict()
		neg_list = list()
		pair_list = []
		for i in a:
			i = int(i)
			if i > 0:
				if i in pos_dict:
					pos_dict[i] += 1
				else:
					pos_dict[i] = 1
			else:
				neg_list.append(i)
		neg_list.sort(reverse=True)
		for i in neg_list:
			if -i in pos_dict and pos_dict[-i] > 0:
				pair_list.append(i)
				pair_list.append(-i)
				pos_dict[-i] -= 1
		return pair_list


class Solution:

	def PosNegPair(self, a, n):
		pos_dict = dict()
		neg_dict = dict()
		pair_list = []
		for i in a:
			i = int(i)
			if i > 0:
				if i in pos_dict:
					pos_dict[i] += 1
				else:
					pos_dict[i] = 1
			elif i in neg_dict:
				neg_dict[i] += 1
			else:
				neg_dict[i] = 1
		for key in pos_dict.keys():
			if -key in neg_dict:
				min_val = min(neg_dict[-key], pos_dict[key])
				if -key in neg_dict:
					min_val = min(neg_dict[-key], pos_dict[key])
					pair_list.extend([key] * (min_val * 2))
		pair_list.sort()
		for i in range(len(pair_list)):
			if i % 2 == 0:
				pair_list[i] = -pair_list[i]
		return pair_list


from collections import Counter

class Solution:

	def PosNegPair(self, a, n):
		(pos, neg) = ([], [])
		final = []
		for i in a:
			i = int(i)
			if i < 0:
				neg.append(i)
			else:
				pos.append(i)
		pc = Counter(pos)
		nc = Counter(neg)
		for (key, val) in pc.items():
			if -key in nc:
				x = min(val, nc[-key])
				for i in range(x * 2):
					final.append(key)
		final.sort()
		for i in range(len(final)):
			if i % 2 == 0:
				final[i] = -final[i]
		return final


from collections import Counter

class Solution:

	def PosNegPair(self, a, n):
		positive = []
		negetive = []
		final = []
		for i in a:
			i = int(i)
			if i < 0:
				negetive.append(i)
			else:
				positive.append(i)
		pos1 = Counter(positive)
		neg1 = Counter(negetive)
		for (key, value) in pos1.items():
			if -key in neg1:
				x = min(value, neg1[-key])
				for i in range(x * 2):
					final.append(key)
		final = sorted(final)
		for i in range(len(final)):
			if i % 2 == 0:
				final[i] = -final[i]
		return final


from collections import Counter

class Solution:

	def PosNegPair(self, a, n):
		positive = []
		negetive = []
		final = []
		for i in a:
			i = int(i)
			if i < 0:
				negetive.append(i)
			else:
				positive.append(i)
		pos1 = Counter(positive)
		negetive = sorted(negetive)
		negetive = negetive[::-1]
		for i in range(len(negetive)):
			if -negetive[i] in pos1:
				if pos1[-negetive[i]] > 0:
					final.append(negetive[i])
					final.append(-negetive[i])
					pos1[-negetive[i]] -= 1
		return final


from collections import defaultdict

class Solution:

	def PosNegPair(self, a, n):
		a = list(map(int, a))
		a.sort()
		c = 0
		for i in range(0, n):
			if int(a[i]) > 0:
				c = i
				break
		d = defaultdict(lambda : 0)
		for i in a:
			if int(i) < 0:
				d[int(i)] += 1
		l = []
		for i in range(c, n):
			x = int(a[i]) * -1
			if d[x] > 0:
				l.append(x)
				l.append(int(a[i]))
				d[x] -= 1
		return l


class Solution:

	def PosNegPair(self, a, n):
		ans = []
		gg = {}
		for i in a:
			if i in gg:
				gg[i] += 1
			else:
				gg[i] = 1
		pos = []
		for i in a:
			if int(i) >= 0:
				pos.append(int(i))
		pos.sort()
		for i in pos:
			i = str(i)
			while gg[i] > 0:
				l = str(-int(i))
				if l in gg.keys() and gg[l] > 0:
					ans.append(l)
					ans.append(i)
					gg[i] -= 1
					gg[l] -= 1
				else:
					gg[i] -= 1
		return ans


class Solution:

	def PosNegPair(self, a, n):
		A = [int(i) for i in a]
		hash_map = {}
		for i in a:
			val = int(i)
			if val < 0:
				if val in hash_map:
					hash_map[val] += 1
				else:
					hash_map[val] = 1
		A.sort()
		ans = []
		for i in A:
			val = int(i)
			negval = val * -1
			if val > 0:
				if negval in hash_map:
					ans.append(negval)
					ans.append(val)
					hash_map[negval] -= 1
					if hash_map[negval] == 0:
						del hash_map[negval]
		return ans


class Solution:

	def PosNegPair(self, a, n):
		res = []
		p = []
		m = {}
		for i in a:
			q = int(i)
			m[q] = m.get(q, 0) + 1
		for i in a:
			g = int(i)
			if m.get(g) > 0 and m.get(-g, 0) > 0:
				if g > 0:
					p.append(g)
				else:
					p.append(-g)
			m[g] = m.get(g) - 1
			m[-g] = m.get(-g, 0) - 1
		p.sort()
		for i in p:
			res.append(-i)
			res.append(i)
		return res


class Solution:

	def PosNegPair(self, aa, n):
		a = []
		for i in range(n):
			a.append(int(aa[i]))
		a.sort()
		i = 0
		l = []
		z = 0
		for i in range(n):
			if a[i] > 0:
				z = i
				break
		i = z - 1
		j = z
		if z == 0:
			return l
		else:
			while i > -1 and j < n:
				if -a[i] == a[j]:
					l.append(a[i])
					l.append(a[j])
					i = i - 1
					j = j + 1
				elif -a[i] < a[j]:
					i = i - 1
				elif -a[i] > a[j]:
					j = j + 1
		return l


class Solution:

	def PosNegPair(self, a, n):
		s = set()
		s1 = []
		a = [int(x) for x in a]
		stack = []
		ans = []
		arr = list(sorted(a, key=lambda y: (abs(y), y)))
		for (i, x) in enumerate(arr):
			if i == 0:
				stack.append(x)
				continue
			if x < 0:
				stack.append(x)
				continue
			if stack and stack[-1] != -x:
				stack = []
				stack.append(x)
			elif stack and stack[-1] == -x:
				ans.append(stack.pop())
				ans.append(x)
		return ans