Read problems statements in Mandarin Chinese and Russian as well. 

Today is Devu's birthday. He has obtained few colored balloons from his friends. You are given this information by a string s consisting of lower case English Latin letters. Each letter (from 'a' to 'z')  denotes a color. e.g. if s = "aab", then it means that he has received two balloons of color 'a' whereas one balloon of color 'b'.

Now, Devu wants to decorate the cake by arranging all the balloons linearly from left to right on the cake such that no same colored balloons are nearby/ adjacent to each other.

Now Devu wonders whether it is possible to do so or not? Please help him in this. If it is not possible to do so, print -1. Otherwise, print any one of arrangements of the balloons on the cake. If there are more than one possible ways of doing so, you can print any one of them. 

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line of each test case will contain string s

------ Output ------ 

Print a single line corresponding to the answer of the problem.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ size of string s  ≤ 10^{5}$
$Sum of size of string s over all test cases will be less than or equal to ≤ 10^{6}$

----- Sample Input 1 ------ 
3
aab
ab
aa
----- Sample Output 1 ------ 
aba
ab
-1
----- explanation 1 ------ 
Example case 1. He can arrange the balloons in the order given by the following string "aba". 
Example case 2. He can arrange the balloons in the order given by the following string "ab"
Example case 3. There is no valid way of decorating cakes with balloon in the desired way. So we print -1.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	s = list(input())
	s.sort()
	n = len(s)
	s.append('0')
	l = []
	(a, c) = (s[0], 1)
	for i in range(1, n + 1):
		if s[i] != s[i - 1]:
			l.append([a, c])
			(a, c) = (s[i], 1)
		else:
			c += 1
	s1 = ''
	a = max(l, key=lambda x: x[1])
	a1 = l.index(a)
	while len(l) > 1:
		p = a[:]
		s1 += p[0]
		p[1] -= 1
		del l[a1]
		a = max(l, key=lambda x: x[1])
		a1 = l.index(a)
		if p[1] > 0:
			l.append(p)
	if l[0][1] == 1:
		s1 += l[0][0]
		print(s1)
	else:
		print(-1)


import heapq
for _ in range(int(input())):
	dic = {}
	temp = []
	ans = ''
	s = input()
	for i in s:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	heapq.heapify(temp)
	for i in dic:
		heapq.heappush(temp, [-dic[i], i])
	condition = True
	ny = True
	useless = ''
	while condition:
		if not temp:
			condition = False
			continue
		if temp[0][1] != useless:
			ans += temp[0][1]
			useless = temp[0][1]
			mx = heapq.heappop(temp)
			if mx[0] != -1:
				heapq.heappush(temp, [mx[0] + 1, mx[1]])
			else:
				heapq.heapify(temp)
		elif len(temp) > 1:
			ans += temp[1][1]
			useless = temp[1][1]
			mx = temp.pop(1)
			if mx[0] != -1:
				heapq.heappush(temp, [mx[0] + 1, mx[1]])
			else:
				heapq.heapify(temp)
		else:
			ny = False
			condition = False
	if ny == True:
		print(ans)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	s = input()
	hash = {}
	yo = ''
	maxi = -10
	for i in s:
		try:
			hash[i]
		except:
			hash[i] = 1
		else:
			hash[i] += 1
	ans = []
	j = 0
	for i in hash.keys():
		ans.append(list(i * hash[i]))
		j += 1
	k = []
	i = 0
	j = 0
	count = 0
	while True:
		if i < len(ans[j]):
			k.append(ans[j][i])
			count += 1
		if count == len(s):
			break
		if j + 1 >= len(ans):
			j = 0
			i += 1
		else:
			j += 1
	bo = []
	ha = 0
	ka = ''
	for i in range(len(k) - 1):
		if k[i] == k[i + 1]:
			ha = i
			ka = k[i]
			break
	count = len(k[i:])
	bo = k[:i]
	yo = []
	la = 0
	for i in range(len(bo) - 1):
		if bo[i] != ka and bo[i + 1] != ka and (la < count):
			yo.append(bo[i])
			yo.append(ka)
			la += 1
		else:
			yo.append(bo[i])
	if bo != []:
		yo.append(bo[-1])
		if len(yo) < len(k):
			if ka != yo[0]:
				yo.insert(0, ka)
		if len(yo) < len(k):
			if ka != yo[-1]:
				yo.insert(len(yo), ka)
	flag = 0
	flag1 = 0
	for i in range(len(k) - 1):
		if k[i] != k[i + 1]:
			continue
		else:
			flag = 1
			break
	if flag == 1:
		for i in range(len(yo) - 1):
			if yo[i] != yo[i + 1]:
				continue
			else:
				flag1 = 1
				break
		if flag1 == 1 or len(yo) != len(k):
			print(-1)
		else:
			print(''.join(yo))
	else:
		print(''.join(k))


from heapq import *
for _ in range(int(input())):
	s = input()
	freq = {}
	for i in s:
		freq[i] = freq.get(i, 0) + 1
	h = []
	for i in freq:
		heappush(h, (-freq[i], i))
	ans = '#'
	while h:
		(f, ch) = heappop(h)
		f = -f
		if not h:
			if f > 1 or ans[-1] == ch:
				ans = -1
			else:
				ans += ch
			break
		(f2, ch2) = heappop(h)
		f2 = -f2
		if ans[-1] == ch:
			ans += ch2 + ch
		else:
			ans += ch + ch2
		f -= 1
		f2 -= 1
		if f > 0:
			heappush(h, (-f, ch))
		if f2 > 0:
			heappush(h, (-f2, ch2))
	if ans == -1:
		print(-1)
	else:
		print(ans[1:])


from collections import Counter
for _ in range(int(input())):
	s = input()
	n = len(s)
	ct = Counter(s)
	a = []
	for (k, v) in ct.most_common():
		a.extend(k * v)
	h = (n - 1) // 2 + 1
	buf = [0] * n
	p = 0
	for i in range(0, n, 2):
		buf[i] = a[p]
		p += 1
	for i in range(1, n, 2):
		buf[i] = a[p]
		p += 1
	ok = True
	for i in range(n - 1):
		if buf[i] == buf[i + 1]:
			ok = False
	print(''.join(buf) if ok else '-1')