Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given a string s with length n. You should find a permutation P of numbers 1 through n such that if you apply this permutation on the string s, you will get a palindromic string.

The result of applying a permutation P on the string s is a string t with length n such that for each i (1 ≤ i ≤ n), the i-th character of t is given as as t[i] = s[P_{i}].

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

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains the string s.

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

For each test case, print a single line. If it is impossible to find a valid permutation P, this line should contain a single integer -1. Otherwise, it should contain n space-separated integers P_{1}, P_{2}, ..., P_{n}.

If there are multiple valid permutations, you may print any one.

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

$1 ≤ n ≤ 10^{5}$
$s will consist only of lowercase English letters (i.e. characters 'a' through 'z')$

------ Subtasks ------ 

Subtask #1 (20 points): 1 ≤ T, n ≤ 10
Subtask #2 (20 points): 1 ≤ T, n ≤ 100
Subtask #3 (60 points): 1 ≤ T ≤ 10

----- Sample Input 1 ------ 
4
aa
baa
abc
abab
----- Sample Output 1 ------ 
1 2
2 1 3
-1
1 2 4 3
----- explanation 1 ------ 
Example case 1: The string t obtained using the identity permutation will have t[1] = s[1] and t[2] = s[2]. That means t = "aa", which is a palindrome.

Example case 2: The characters of the string t obtained by applying the permutation 2, 1, 3 are t[1] = s[2], t[2] = s[1] and t[3] = s[3]. Therefore, t = "aba", which is a palindrome.

Example case 3: There is no way to find a permutation P such that we can obtain a palindrome from s using it.

Example case 4: Applying the permutation 1, 2, 4, 3 on s results in t = "abba", which is a palindrome. Another permutation that you may apply is 2, 1, 3, 4; this results in t = "baab", which is also a palindrome.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
from typing import List
from collections import Counter

def palin_perm(s: str) -> List[int]:
	n = len(s)
	counts = Counter(s)
	odds = 0
	for count in counts.values():
		if count & 1:
			odds += 1
	if n & 1 and odds > 1 or (not n & 1 and odds > 0):
		return [-1]
	inds = {i: [] for i in s}
	for i in range(n):
		inds[s[i]].append(i + 1)
	res = [-1] * n
	if n & 1:
		for (key, val) in counts.items():
			if val & 1:
				let = key
				poses = inds[key]
				del inds[key]
		i = 0
		for pos in inds.values():
			while pos:
				res[i] = pos.pop()
				res[n - i - 1] = pos.pop()
				i += 1
		for x in poses:
			res[i] = x
			i += 1
	else:
		i = 0
		for pos in inds.values():
			while pos:
				res[i] = pos.pop()
				res[n - i - 1] = pos.pop()
				i += 1
	return res
for _ in range(int(input())):
	s = input()
	print(*palin_perm(s))


for _ in range(int(input())):
	srng = input()
	srli = list(srng)
	n = len(srli)
	lst = list()
	odd = 0
	oddli = []
	dct = {}
	psbl = True
	for i in range(n):
		if srli[i] in dct.keys():
			dct[srli[i]].append(i + 1)
		else:
			dct[srli[i]] = [i + 1]
	for (key, value) in dct.items():
		if len(value) % 2 == 0:
			md = len(lst) // 2
			lst = lst[:md] + value + lst[md:]
		else:
			odd += 1
			oddli = value
			if odd > 1:
				psbl = False
				break
	if psbl:
		if odd == 0:
			print(*lst)
		else:
			md = len(lst) // 2
			lst = lst[:md] + oddli + lst[md:]
			print(*lst)
	else:
		print(-1)


for z in range(int(input())):
	s = input()
	n = len(s)
	d = {i: [] for i in range(26)}
	for i in range(len(s)):
		d[ord(s[i]) - 97].append(i)
	j = -1
	k = 0
	for x in d.keys():
		if len(d[x]) % 2 != 0:
			j = x
			k += 1
	if k > 1:
		print(-1)
		continue
	l = 0
	r = n - 1
	b = [0] * n
	if k == 1:
		b[n // 2] = str(1 + d[j][0])
		d[j].pop(0)
	k = 0
	while l < r:
		for i in range(0, len(d[k]) - 1, 2):
			b[l] = str(1 + d[k][i])
			b[r] = str(1 + d[k][i + 1])
			l += 1
			r -= 1
			if l >= r:
				break
		k += 1
	print(' '.join(b))


n = int(input())
for p in range(n):
	s = input()
	d = {}
	for i in range(len(s)):
		lst = []
		if s[i] in d:
			lst = d[s[i]]
			lst.append(i)
		else:
			lst = [i]
			d.update({s[i]: lst})
	ans = [0] * len(s)
	i = 0
	j = len(s) - 1
	count_o = 0
	count_e = 0
	for i in d.keys():
		if len(d[i]) % 2 == 0:
			count_e += 1
		else:
			count_o += 1
	if count_o > 1:
		print(-1)
	else:
		i = 0
		j = len(s) - 1
		for l in range(len(s)):
			lst = d[s[l]]
			if len(lst) % 2 == 0:
				k = 0
				while k < len(lst):
					ans[i] = lst[k] + 1
					k += 1
					ans[j] = lst[k] + 1
					k += 1
					i += 1
					j -= 1
				lst = []
				d[s[l]] = lst
			else:
				k = 1
				while k < len(lst):
					ans[i] = lst[k - 1] + 1
					k += 1
					ans[j] = lst[k - 1] + 1
					k += 1
					i += 1
					j -= 1
				ans[len(s) // 2] = lst[len(lst) - 1] + 1
				lst = []
				d[s[l]] = lst
		print(*ans)


from collections import Counter, defaultdict

def check(c):
	f = False
	o = -1
	for (k, v) in c.items():
		if v % 2:
			if f:
				return False
			f = True
			o = k
	return o
for _ in range(int(input())):
	l = list(input())
	n = len(l)
	c = Counter(l)
	o = check(c)
	if not o:
		print(-1)
	else:
		d = defaultdict(list)
		for i in range(n):
			d[l[i]].append(i)
		(f, b) = ([], [])
		for (k, v) in d.items():
			if k != o:
				nv = len(v)
				for i in range(nv // 2):
					f.append(v[i] + 1)
				for i in range(nv // 2, nv):
					b.append(v[i] + 1)
		if o != -1:
			for i in d[o]:
				f.append(i + 1)
		ans = f + b[::-1]
		print(*ans)


from collections import defaultdict
for _ in range(int(input())):
	ip = input()
	count = [0] * 26
	mp = defaultdict(list)
	for i in range(len(ip)):
		count[ord(ip[i]) - ord('a')] += 1
		mp[ip[i]].append(i + 1)
	odd_count = 0
	for i in range(26):
		if count[i] % 2 == 1:
			odd_count += 1
	if odd_count > 1:
		print(-1)
		continue
	emp = [0] * len(ip)
	l = 0
	r = len(emp) - 1
	startIndex = 0
	for i in range(26):
		if count[i] % 2 != 1 and count[i] > 0:
			currcount = count[i]
			for j in range(0, currcount, 2):
				emp[startIndex] = mp[chr(i + ord('a'))][j]
				emp[len(emp) - startIndex - 1] = mp[chr(i + ord('a'))][j + 1]
				startIndex += 1
	for i in range(26):
		if count[i] % 2 == 1:
			currcount = count[i]
			for j in range(currcount):
				emp[startIndex] = mp[chr(i + ord('a'))][j]
				startIndex += 1
	print(*emp)


def printPalindromicStr(s):
	d = {}
	n = 0
	for i in s:
		if d.get(i) == None:
			d[i] = []
		d[i].append(n)
		n += 1
	oddfreq = 0
	for i in d:
		if len(d[i]) % 2 != 0:
			oddfreq += 1
	if oddfreq > 1:
		print('-1')
		return
	ans = [0 for i in range(n)]
	si = 0
	li = n - 1
	for i in d:
		l = len(d[i])
		if l % 2 != 0:
			ans[n // 2] = d[i][-1]
			l -= 1
		for j in range(0, l, 2):
			ans[si] = d[i][j]
			ans[li] = d[i][j + 1]
			si += 1
			li -= 1
	for i in ans:
		print(i + 1, end=' ')
	print()
	return
t = int(input())
while t:
	t -= 1
	printPalindromicStr(input())


from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
from pickle import FALSE
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
from tkinter.tix import Tree
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
for _ in rg(ii()):
	s = ip()
	d = {}
	for l in range(len(s)):
		if s[l] in d:
			d[s[l]].append(l + 1)
		else:
			d[s[l]] = [l + 1]
	odd = False
	ans = False
	for k in d:
		if len(d[k]) % 2 != 0:
			if odd:
				ans = True
				print(-1)
				break
			else:
				odd = not odd
	res1 = []
	res2 = []
	o = []
	if not ans:
		for k in d:
			if len(d[k]) % 2 == 0:
				while len(d[k]) > 0:
					res1.append(d[k].pop())
					res2.append(d[k].pop())
			else:
				while len(d[k]) > 0:
					o.append(d[k].pop())
		res = res1 + o + res2[::-1]
		print(*res)


def makestring(arr, n):
	dic = {}
	for i in range(n):
		if dic.get(arr[i], -1) == -1:
			dic[arr[i]] = [i + 1]
		else:
			dic[arr[i]] = dic[arr[i]] + [i + 1]
	odd = 0
	char = False
	for i in dic:
		if len(dic[i]) % 2 != 0:
			odd += 1
			char = i
	if odd > 1:
		return [-1]
	strg = []
	if char:
		strg = dic[char]
	for i in dic:
		if i is not char:
			length = len(dic[i]) // 2
			strg = dic[i][:length] + strg + dic[i][length:]
	return strg
t = int(input())
for _ in range(t):
	arr = input()
	strg = makestring(arr, len(arr))
	print(*strg)


def makedic(arr):
	dic = {}
	for i in range(len(arr)):
		if dic.get(arr[i], -1) == -1:
			dic[arr[i]] = [i + 1]
		else:
			dic[arr[i]] = dic[arr[i]] + [i + 1]
	return dic

def check(dic):
	odd = 0
	char = True
	for i in dic:
		if len(dic[i]) % 2 != 0:
			odd += 1
			char = i
	if odd > 1:
		char = False
	return char

def makestring(char, dic, n):
	if char == False:
		return -1
	else:
		strg = []
		if char != True:
			strg = strg + dic[char]
			del dic[char]
		for i in dic:
			length = len(dic[i]) // 2
			strg = dic[i][:length] + strg + dic[i][length:]
	return strg
t = int(input())
for _ in range(t):
	arr = input()
	dic = makedic(arr)
	char = check(dic)
	strg = makestring(char, dic, len(arr))
	if strg == -1:
		print(strg)
	else:
		print(*strg)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	l = len(s)
	i = 0
	j = l - 1
	while i < j:
		if s[i] != s[j]:
			return False
		else:
			i += 1
			j -= 1
	return True

def solve(t):
	s = readStr()
	n = len(s)
	ind = {}
	res = ['' for _ in range(n)]
	for i in range(n):
		c = s[i]
		if c in ind:
			ind[c].append(i + 1)
		else:
			ind[c] = [i + 1]
	flag = False
	k = 0
	for char in ind:
		if len(ind[char]) & 1 and (not len(ind[char]) & 1 or flag):
			print(-1)
			return None
		if not len(ind[char]) & 1:
			for i in range(0, len(ind[char]), 2):
				res[k] = ind[char][i]
				res[n - k - 1] = ind[char][i + 1]
				k += 1
		else:
			for i in range(0, len(ind[char]) - 1, 2):
				res[k] = ind[char][i]
				res[n - k - 1] = ind[char][i + 1]
				k += 1
			res[n // 2] = ind[char][-1]
			flag = True
	print(*res)

def main():
	t = 1
	sys.setrecursionlimit(12000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


def solve(string):
	counts = [0] * 26
	ans = [None] * len(string)
	hashmap = {}
	odd = 0
	for i in range(len(string)):
		if string[i] not in hashmap:
			hashmap[string[i]] = [i + 1]
		else:
			hashmap[string[i]].append(i + 1)
		counts[ord(string[i]) - ord('a')] += 1
	for i in range(len(counts)):
		if counts[i] & 1:
			odd += 1
		if odd > 1:
			return [-1]
	left = 0
	right = len(string) - 1
	for i in hashmap:
		if len(hashmap[i]) & 1:
			start_index = len(string) // 2 - len(hashmap[i]) // 2
			for j in range(len(hashmap[i])):
				ans[start_index] = hashmap[i][j]
				start_index += 1
		else:
			for j in range(len(hashmap[i]) // 2):
				ans[left] = hashmap[i][j]
				ans[right] = hashmap[i][len(hashmap[i]) - 1 - j]
				left += 1
				right -= 1
	return ans
t = int(input())
while t > 0:
	strings = input()
	for i in solve(strings):
		print(i, end=' ')
	print('\n')
	t -= 1


t = int(input())
while t > 0:
	st = input()
	n = len(st)
	co = [0] * 27
	ne = [0] * n
	ind = [0] * n
	ma = [0] * n
	for i in range(n):
		x = ord(st[i]) - 97
		co[x] += 1
	c1 = 0
	c2 = 0
	for i in range(26):
		if co[i] % 2 == 0:
			c2 += 1
		else:
			c1 += 1
	if n % 2 == 0:
		if c1 > 0:
			print('-1')
		else:
			ar = [[] for i in range(26)]
			new = [0] * n
			for i in range(n):
				x = ord(st[i]) - 97
				ar[x].append(i + 1)
			j = 0
			le = 0
			for i in range(26):
				while len(ar[j]) > 1:
					x = ar[j].pop()
					new[le] = x
					x = ar[j].pop()
					new[n - le - 1] = x
					le = le + 1
				j = j + 1
			for i in range(n):
				print(new[i], end=' ')
			print()
	elif n % 2 == 1:
		if c1 > 1:
			print('-1')
		else:
			ar = [[] for i in range(26)]
			new = [0] * n
			for i in range(n):
				x = ord(st[i]) - 97
				ar[x].append(i + 1)
			j = 0
			le = 0
			for i in range(26):
				while len(ar[j]) > 1:
					x = ar[j].pop()
					new[le] = x
					x = ar[j].pop()
					new[n - le - 1] = x
					le = le + 1
				j = j + 1
			for i in range(26):
				if len(ar[i]) == 1:
					x = ar[i].pop()
					break
			new[n // 2] = x
			for i in range(n):
				print(new[i], end=' ')
			print()
	t = t - 1


def form_palindrome(frequencies, indices):
	length = sum(frequencies.values())
	frequencies = dict(sorted(frequencies.items(), key=lambda x: x[1], reverse=True))
	odd = None
	for (key, value) in frequencies.items():
		if value % 2:
			odd = key
	new_string = [' '] * sum(frequencies.values())
	indexes = [None for _ in range(length)]
	current = 0
	for (key, value) in frequencies.items():
		for j in range(value // 2):
			new_string[current] = key
			new_string[length - current - 1] = key
			indexes[current] = str(indices[key][0] + 1)
			indexes[length - current - 1] = str(indices[key][1] + 1)
			del indices[key][0]
			del indices[key][0]
			current += 1
	if odd:
		indexes[current] = str(indices[odd][0] + 1)
	return ' '.join(indexes)
for _ in range(int(input())):
	s = input()
	frequencies = {}
	index_frequencies = {}
	for (i, char) in enumerate(s):
		if frequencies.get(char):
			frequencies[char] += 1
		else:
			frequencies[char] = 1
		if index_frequencies.get(char):
			index_frequencies[char].append(i)
		else:
			index_frequencies[char] = [i]
	values = list(frequencies.values())
	if len(s) % 2:
		odd_values = list(filter(lambda x: x % 2, values))
		if len(odd_values) == 1:
			print(form_palindrome(frequencies, index_frequencies))
		else:
			print(-1)
	else:
		odd_values = list(filter(lambda x: x % 2, values))
		if len(odd_values):
			print(-1)
		else:
			print(form_palindrome(frequencies, index_frequencies))


for _ in range(int(input())):
	s = input()
	if s == s[::-1]:
		print(*list(range(1, len(s) + 1)))
	else:
		d = {}
		for i in range(len(s)):
			if s[i] not in d.keys():
				d[s[i]] = [i + 1]
			else:
				d[s[i]].append(i + 1)
		cnt = 0
		for i in d.values():
			if len(i) % 2 == 1:
				cnt += 1
		if cnt >= 2:
			print(-1)
		else:
			p = [0] * len(s)
			index = 0
			for l in d.values():
				if len(l) % 2 == 0:
					for j in range(0, len(l), 2):
						p[index] = l[j]
						p[len(p) - 1 - index] = l[j + 1]
						index += 1
				else:
					odd = l
			if cnt == 1:
				mid = (len(s) - len(odd)) // 2
				p = p[0:mid:1] + odd + p[mid + len(odd):]
			print(*p)


from collections import defaultdict
t = int(input())
for _ in range(t):
	inp_str = input().strip()
	mp = defaultdict(int)
	mp_ix = defaultdict(list)
	for (i, c) in enumerate(inp_str):
		mp[c] += 1
		mp_ix[c].append(i)
	ec = 0
	oc = 0
	for (_, v) in mp.items():
		ec += 1 if v % 2 == 0 else 0
		oc += 0 if v % 2 == 0 else 1
	if oc > 1:
		print(-1)
		continue
	else:
		left = []
		right = []
		k1 = ''
		v1 = 0
		for (k, v) in mp.items():
			if v % 2 == 0:
				for _ in range(v // 2):
					left.append(k)
					right.append(k)
			else:
				(k1, v1) = (k, v)
		if v1 % 2 == 1:
			for _ in range(v1 // 2):
				left.append(k1)
				right.append(k1)
			right.append(k1)
		perm = []
		pallin = left + right[::-1]
		for c in pallin:
			perm.append(mp_ix[c][0] + 1)
			mp_ix[c].pop(0)
		print(*perm, sep=' ')


import math as m
t = int(input())
for _ in range(t):
	word = input()
	length = len(word)
	count = {}
	position = {}
	for index in range(len(word)):
		character = word[index]
		count[character] = count.get(character, 0) + 1
		if position.get(character, False) == False:
			position[character] = [index]
		else:
			position[character].append(index)
	oddCount = 0
	oddCharacter = ''
	for index in range(26):
		currCharacter = chr(index + 97)
		if count.get(currCharacter, 0) % 2 == 1:
			oddCount += 1
			oddCharacter = currCharacter
	if oddCount >= 2:
		print(-1)
		continue
	pal = [None] * length
	startIndex = 0
	for ascii in range(97, 123):
		currCharacter = chr(ascii)
		countOfCurrent = count.get(currCharacter, 0)
		if countOfCurrent % 2 == 0 and countOfCurrent > 0:
			currLen = len(position[currCharacter])
			for j in range(0, currLen, 2):
				pal[startIndex] = position[currCharacter][j]
				pal[length - startIndex - 1] = position[currCharacter][j + 1]
				startIndex += 1
	if oddCount == 1:
		size = len(position[oddCharacter])
		for j in range(0, size):
			pal[startIndex] = position[oddCharacter][j]
			startIndex += 1
	for value in pal:
		print(value + 1, end=' ')
	print()


def permutation(string):
	dic = {}
	c = 0
	n = len(string)
	for (i, j) in enumerate(string):
		try:
			dic[j].append(i + 1)
		except:
			dic[j] = [i + 1]
	for i in dic:
		if len(dic[i]) % 2 != 0:
			c += 1
	if c >= 2:
		return -1
	end = n - 1
	ans = list(range(n))
	start = 0
	string = 'abcdefghijklmnopqrstuvwxyz'
	for i in string:
		try:
			if len(dic[i]) % 2 != 0:
				ans[n // 2 - len(dic[i]) // 2:n // 2 - len(dic[i]) // 2 + len(dic[i])] = dic[i]
				continue
			for j in range(0, len(dic[i]), 2):
				ans[start] = dic[i][j]
				ans[end] = dic[i][j + 1]
				start += 1
				end -= 1
		except:
			continue
	return ans
t = int(input())
while t > 0:
	t -= 1
	string = input()
	out = permutation(string)
	if out == -1:
		print(-1)
	else:
		for i in out[:-1]:
			print(i, end=' ')
		print(out[-1])


def printpalin(s):
	n = len(s)
	m = dict()
	for i in range(n):
		if s[i] in m:
			m[s[i]].append(i)
		else:
			m[s[i]] = [i]
	odd_count = 0
	for i in m.values():
		if len(i) % 2 == 1:
			odd_count += 1
			if odd_count >= 2:
				print(-1)
				return
	arr = [0] * n
	x = 0
	y = n - 1
	for i in m.values():
		for j in range(0, len(i), 2):
			if len(i) - j == 1:
				arr[n // 2] = i[j] + 1
				continue
			arr[x] = i[j] + 1
			arr[y] = i[j + 1] + 1
			x += 1
			y -= 1
	for i in arr:
		print(i, end=' ')
	print()
	return
t = int(input())
for _ in range(t):
	s = input()
	printpalin(s)


def permutation(s):
	ref = [0 for i in range(26)]
	index = [[] for i in range(26)]
	iter = 0
	for i in s:
		iter += 1
		ref[ord(i) - 97] += 1
		index[ord(i) - 97].append(iter)
	first_odd = -1
	for i in range(26):
		if ref[i] % 2 == 1:
			if first_odd != -1 or len(s) % 2 == 0:
				return [-1]
			else:
				first_odd = i
	ans_forward = []
	ans_reverse = []
	for i in range(26):
		if i != first_odd:
			for j in range(0, len(index[i]), 2):
				ans_forward.append(index[i][j])
				ans_reverse.append(index[i][j + 1])
	if first_odd != -1:
		if ref[first_odd] == 1:
			ans_forward.append(index[first_odd][0])
		else:
			for j in range(0, len(index[first_odd]) - 1, 2):
				ans_forward.append(index[first_odd][j])
				ans_reverse.append(index[first_odd][j + 1])
			ans_forward.append(index[first_odd][-1])
	return ans_forward + ans_reverse[::-1]
import sys
c = 0
for line in sys.stdin:
	if c == 0:
		t = int(line.strip())
		c = 2
	else:
		qn = line.strip()
		c += 1
		print(*permutation(qn))


from collections import defaultdict, deque
try:
	for _ in range(int(input())):
		inpText = input()
		length = len(inpText)
		count = defaultdict(deque)
		for idx in range(len(inpText)):
			count[inpText[idx]].append(str(idx + 1))
		oddChars = list(filter(lambda char: len(count[char]) % 2 != 0, count.keys()))
		if length % 2 == 0:
			if len(oddChars) != 0:
				print(-1)
				continue
			keys = deque(count.keys())
			outputSeq = deque(count.pop(keys.popleft()))
			for key in keys:
				pos = count[key]
				while len(pos) != 0:
					outputSeq.appendleft(pos.popleft())
					outputSeq.append(pos.pop())
		else:
			if len(oddChars) > 1:
				print(-1)
				continue
			outputSeq = deque(count.pop(oddChars[0]))
			keys = deque(count.keys())
			for key in keys:
				pos = count[key]
				while len(pos) != 0:
					outputSeq.appendleft(pos.popleft())
					outputSeq.append(pos.pop())
		outputSeq = ' '.join(outputSeq)
		print(outputSeq)
except EOFError:
	pass


from collections import defaultdict
t = int(input())
for _ in range(t):
	s = input()
	h = defaultdict(list)
	for i in range(len(s)):
		h[s[i]].append(i + 1)
	c = 0
	for i in set(s):
		if len(h[i]) % 2 == 1:
			c = c + 1
	r1 = []
	r2 = []
	o = []
	if c <= 1:
		for i in set(s):
			l = h[i]
			if len(l) % 2 == 0:
				r1 = r1 + l[:len(l) // 2]
				r2 = r2 + l[len(l) // 2:]
			else:
				o = o + h[i]
		print(*r1[::-1] + o + r2)
	else:
		print(-1)


T = int(input())
for i in range(T):
	s = input()
	h = {}
	r = [0] * len(s)
	n = len(s)
	for i in range(len(s)):
		if s[i] in h:
			h[s[i]].append(i + 1)
		else:
			h[s[i]] = []
			h[s[i]].append(i + 1)
	c = 0
	for i in h:
		if len(h[i]) % 2 == 1:
			c += 1
	k = 0
	if c == 1 or c == 0:
		for i in h:
			x = h[i]
			m = len(x) // 2
			j = 0
			while m:
				r[k] = x[j]
				r[-k - 1] = x[-j - 1]
				j += 1
				k += 1
				m = m - 1
			if len(x) % 2 == 1:
				r[n // 2] = x[len(x) // 2]
		print(*r)
	else:
		print(-1)


n = int(input())
for t in range(n):
	string = input()
	ansDict = {}
	indexDict = {}
	for idx in range(len(string)):
		char = string[idx]
		ansDict[char] = ansDict.get(char, 0) + 1
		if indexDict.get(char) is None:
			charList = [idx]
			indexDict[char] = charList
		else:
			indexDict[char].append(idx)
	oddCount = 0
	oddChar = None
	for (char, freq) in ansDict.items():
		if freq % 2 != 0:
			oddCount += 1
			oddChar = char
	if oddCount == 0 or oddCount == 1:
		(i, j) = (0, -1)
		ansList = [-1] * len(string)
		for (char, value) in indexDict.items():
			li = indexDict[char]
			if ansDict[char] % 2 == 0:
				for k in range(0, len(li), 2):
					ansList[i] = li[k]
					ansList[j] = li[k + 1]
					i += 1
					j -= 1
		if oddCount == 1:
			li = indexDict[oddChar]
			for k in range(0, len(li)):
				if ansList[i] == -1:
					ansList[i] = li[k]
					i += 1
		for ele in ansList:
			print(ele + 1, end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	p = [i for i in range(1, n + 1)]
	i = 0
	j = n - 1
	flag = True
	while i <= j:
		if s[i] != s[j]:
			f = -1
			for k in range(i + 1, j):
				if s[k] == s[j]:
					pos = k
					f = 0
					break
				if s[k] == s[i]:
					pos = k
					f = 1
					break
			if f == -1:
				flag = False
			if f == 0:
				(p[i], p[k]) = (p[k], p[i])
				(s[i], s[k]) = (s[k], s[i])
			if f == 1:
				(p[j], p[k]) = (p[k], p[j])
				(s[j], s[k]) = (s[k], s[j])
		i += 1
		j -= 1
	if flag:
		print(*p, sep=' ')
	else:
		print('-1')


t = int(input())
for _ in range(t):
	s = input()
	lst = {}
	n = len(s)
	for i in range(len(s)):
		if lst.get(s[i]) == None:
			lst[s[i]] = [i + 1]
		else:
			lst[s[i]].append(i + 1)
	count = 0
	for k in lst:
		if len(lst[k]) % 2 == 1:
			count += 1
	if count > 1:
		print(-1)
	else:
		ans = [0] * n
		i = 0
		j = n - 1
		for k in lst:
			if len(lst[k]) % 2 == 0:
				for ind in range(len(lst[k]) // 2):
					ans[i] = lst[k][ind]
					i += 1
				for ind in range(len(lst[k]) // 2, len(lst[k])):
					ans[j] = lst[k][ind]
					j -= 1
			else:
				mid = n // 2
				temp = mid - 1
				ans[mid] = lst[k][0]
				mid += 1
				l = len(lst[k])
				for ind in range(1, l // 2 + 1):
					ans[mid] = lst[k][ind]
					mid += 1
				for ind in range(l // 2 + 1, len(lst[k])):
					ans[temp] = lst[k][ind]
					temp -= 1
		print(*ans)


from collections import deque

def solve(d):
	flag = True
	odd_list = []
	skip_key = ''
	for (key, ele) in d.items():
		if len(ele) % 2 != 0:
			if flag == False:
				print(-1)
				return
			else:
				flag = False
				odd_list = ele
				skip_key = key
	l = deque(odd_list)
	for ele in d:
		if ele == skip_key:
			continue
		for i in range(len(d[ele]) // 2):
			l.appendleft(d[ele][i])
			l.append(d[ele][len(d[ele]) - 1 - i])
	for i in range(len(l) - 1):
		print(l[i], end=' ')
	print(l[-1])
T = int(input())
for i in range(T):
	s = input()
	d = {}
	for j in range(len(s)):
		if s[j] not in d:
			d[s[j]] = []
		d[s[j]].append(j + 1)
	solve(d)


def makeMap(st):
	map = {}
	for i in range(len(st)):
		lis = [i]
		if st[i] not in map:
			map[st[i]] = lis
		else:
			map[st[i]] = map[st[i]] + lis
	return map

def makePallindrome(st):
	n = len(st)
	map = makeMap(st)
	odd_count = 0
	for ele in map:
		if len(map[ele]) % 2 != 0:
			odd_count += 1
	if odd_count >= 2:
		print(-1)
		return
	ans = [-1] * n
	start = 0
	end = n - 1
	for ele in map:
		for j in range(0, len(map[ele]), 2):
			if len(map[ele]) - j == 1:
				ans[len(st) // 2] = map[ele][j]
				continue
			ans[start] = map[ele][j]
			ans[end] = map[ele][j + 1]
			start += 1
			end -= 1
	for ele in ans:
		print(ele + 1, end=' ')
t = int(input())
for i in range(t):
	st = input()
	makePallindrome(st)
	print()


def window(string):
	ref = []
	start = []
	stop = []
	iter = -1
	for i in string:
		iter += 1
		ref.append([i, iter])
	refer = {}
	count = {}
	for i in ref:
		if i[0] in refer.keys():
			refer[i[0]].append(i[1])
			count[i[0]] += 1
		else:
			refer[i[0]] = [i[1]]
			count[i[0]] = 1
	check = 0
	for (key, val) in refer.items():
		if check > 1:
			return [-1]
		if len(val) % 2 == 1:
			check += 1
			track = key
		else:
			for i in range(0, int(len(val) / 2)):
				start.append(val[i] + 1)
			for i in range(int(len(val) / 2), len(val)):
				stop.append(val[i] + 1)
	if len(string) % 2 == 1:
		for i in range(0, int(len(refer[track]) / 2)):
			start.append(refer[track][i] + 1)
		for i in range(int(len(refer[track]) / 2), len(refer[track]) - 1):
			stop.append(refer[track][i] + 1)
		start.append(refer[track][-1] + 1)
	if len(start) + len(stop) != len(string):
		return [-1]
	return start + stop[::-1]
import sys
c = 0
for line in sys.stdin:
	if c == 0:
		t = int(line.strip())
		c = 2
	else:
		qn = line.strip()
		c += 1
		print(*window(qn))


from collections import deque

def window(string):
	ref = {}
	iter = -1
	for i in string:
		iter += 1
		ref.setdefault(i, []).append(iter + 1)
	left = deque([])
	right = []
	extra = -1
	error = False
	for (key, value) in ref.items():
		if len(value) % 2 == 1:
			if iter % 2 == 0 and extra == -1:
				extra = value.pop()
			else:
				error = True
				break
		switch = True
		for item in value:
			if switch:
				left.appendleft(item)
			else:
				right.append(item)
			switch = not switch
	if error:
		return [-1]
	if extra == -1:
		return list(left) + right
	return list(left) + [extra] + right
import sys
c = 0
for line in sys.stdin:
	if c == 0:
		t = int(line.strip())
		c = 2
	else:
		qn = line.strip()
		c += 1
		print(*window(qn))


test = int(input())
for _ in range(test):
	s = input()
	dic = {}
	for u in range(len(s)):
		if s[u] not in dic:
			dic[s[u]] = [u + 1]
		else:
			dic[s[u]] += [u + 1]
	c = 0
	for u in dic.values():
		if len(u) % 2 != 0:
			c += 1
	if c > 1:
		print(-1)
	else:
		k = []
		c = []
		cc = list(dic.values())
		for u in cc:
			if len(u) % 2 != 0:
				k = u.copy()
			else:
				c += u[:len(u) // 2]
		c += k.copy()
		cc.reverse()
		for u in cc:
			if len(u) % 2 != 0:
				continue
			else:
				c += u[len(u) // 2:]
		print(*c)


t = int(input())
while t > 0:
	a = list(input())
	n = len(a)
	s = set(a)
	q = c = 0
	l = [0] * n
	w = ''
	for i in s:
		if a.count(i) % 2 != 0:
			w = a.index(i)
			c += 1
		if c > 1:
			print(-1)
			q = 1
			break
	if q == 0:
		s = 'abcdefghijklmnopqrstuvwxyz'
		k = 0
		if n % 2 != 0:
			l[n // 2] = w + 1
			a[w] = 9
		for i in s:
			c = 0
			for j in range(n):
				if a[j] == i:
					if c % 2 == 0:
						l[k] = j + 1
					else:
						l[n - k - 1] = j + 1
						k += 1
					c += 1
		print(*l)
	t -= 1


from collections import deque
t = int(input())
while t > 0:
	s = input()
	n = len(s)
	ans = ['' for i in range(n)]
	count = [0 for i in range(26)]
	for i in s:
		count[ord(i) - ord('a')] += 1
	count_odd = 0
	for i in count:
		if i % 2 != 0:
			count_odd += 1
	if count_odd > 1:
		print(-1)
	else:
		arr = list(s)
		arr.sort()
		i = 0
		j = 0
		while i < n:
			if count[ord(arr[i]) - ord('a')] % 2 == 0 and count[ord(arr[i]) - ord('a')] > 0:
				ans[j] = arr[i]
				ans[n - j - 1] = arr[i]
				count[ord(arr[i]) - ord('a')] -= 2
				j += 1
				i += 2
			else:
				ans[n // 2] = arr[i]
				count[ord(arr[i]) - ord('a')] -= 1
				i += 1
		temp = ''.join(ans)
		obj = {}
		for i in range(n):
			if s[i] in obj:
				obj[s[i]].append(i)
			else:
				q = deque()
				q.append(i)
				obj[s[i]] = q
		finalAns = []
		for i in temp:
			print(obj[i].popleft() + 1, end=' ')
		print()
	t -= 1


from collections import Counter

def permpal(s):
	n = len(s)
	c = Counter(s)
	t = [0, 0]
	for v in c.values():
		t[v % 2] += 1
	if n % 2:
		if t[1] != 1:
			return -1
	if not n % 2:
		if t[1] != 0:
			return -1
	p = [0 for i in range(n)]
	pos = {}
	for (i, char) in enumerate(s):
		if char not in pos:
			pos[char] = [i + 1]
		else:
			pos[char].append(i + 1)
	if n % 2:
		(i, j) = (n // 2 - 1, n // 2 + 1)
	else:
		(i, j) = (n // 2 - 1, n // 2)
	if n % 2:
		for char in pos:
			if len(pos[char]) % 2:
				p[n // 2] = pos[char].pop()
			while pos[char]:
				(p[i], p[j]) = (pos[char].pop(), pos[char].pop())
				i -= 1
				j += 1
	else:
		for char in pos:
			while pos[char]:
				(p[i], p[j]) = (pos[char].pop(), pos[char].pop())
				i -= 1
				j += 1
	return ' '.join(map(str, p))
t = int(input())
for _ in range(t):
	s = input()
	print(permpal(s))


t = int(input())
for _ in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		try:
			d[s[i]] += [i + 1]
		except:
			d[s[i]] = [i + 1]
	ans = 0
	for i in d.values():
		if len(i) % 2:
			ans += 1
	if ans <= 1:
		x = []
		for i in d.keys():
			if len(d[i]) % 2:
				x = d[i]
				del d[i]
				break
		ans = []
		k = []
		for i in d.keys():
			ans += d[i][:len(d[i]) // 2]
			k += d[i][len(d[i]) // 2:]
		ans += x
		k.reverse()
		ans += k
		print(*ans)
	else:
		print(-1)


from collections import defaultdict

def perm_palin(s):
	chars = defaultdict(list)
	for (index, ch) in enumerate(s, start=1):
		chars[ch].append(index)
	odd_count = 0
	odd_item = None
	for (item, count) in chars.items():
		if len(count) % 2 == 1:
			odd_count += 1
			odd_item = item
	if odd_count >= 2:
		return [-1]
	ans = []
	for (item, count) in chars.items():
		if item != odd_item:
			x = len(ans) // 2
			ans = ans[:x] + count + ans[x:]
	x = len(ans) // 2
	ans = ans[:x] + chars[odd_item] + ans[x:]
	return ans

def main():
	for _ in range(int(input())):
		s = input()
		print(*perm_palin(s))
main()


test_case = int(input())

def assign_res(front, end_st, arr, st1, end1, val):
	i = 0
	st = st1
	end = end1
	while i < len(val):
		arr[st] = val[i] + 1
		front += str(val[i] + 1) + ' '
		arr[end] = val[i + 1] + 1
		end_st = ' ' + str(val[i + 1] + 1)
		st += 1
		end -= 1
		i += 2
	return

def pal_permu(stt):
	freq = {}
	res = [0] * len(stt)
	for i in range(len(stt)):
		if stt[i] in freq.keys():
			freq[stt[i]].append(i)
		else:
			freq[stt[i]] = [i]
	odd = 0
	even = 0
	start = -1
	end = 0
	front = ''
	end_st = ''
	mid_str = ''
	for (key, value) in freq.items():
		if len(value) % 2 == 0:
			start += 1
			end -= 1
			i = 0
			while i < len(value):
				front += str(value[i] + 1) + ' '
				end_st = str(value[i + 1] + 1) + ' ' + end_st
				i += 2
			even += 1
		else:
			odd += 1
	if odd != 1 and odd != 0:
		print('-1')
		return
	for (key, value) in freq.items():
		if len(value) % 2 != 0:
			mid_str = ''
			for i in value:
				mid_str += str(i + 1) + ' '
	mid_str = mid_str[:-1]
	if mid_str != '':
		print(front.strip() + ' ' + mid_str.strip() + ' ' + end_st.strip())
	else:
		print(front.strip() + ' ' + end_st.strip())
	return
for i in range(test_case):
	pal_permu(input())


t = int(input())
for _ in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		if s[i] not in d:
			d[s[i]] = [i]
		else:
			d[s[i]].append(i)
	odd_count = 0
	flag = False
	for i in d:
		if len(d[i]) % 2 != 0:
			odd_count += 1
			if odd_count >= 2:
				flag = True
				break
	if flag:
		print(-1)
	else:
		result = [None] * len(s)
		start = 0
		end = len(s) - 1
		for i in d:
			if len(d[i]) % 2 == 0:
				x = len(d[i]) // 2
				r = -1
				for j in range(x):
					result[start] = d[i][j]
					result[end] = d[i][r]
					r -= 1
					start += 1
					end -= 1
			elif len(d[i]) == 1:
				result[len(s) // 2] = d[i][0]
			else:
				x = len(d[i]) // 2
				r = -1
				for j in range(x):
					result[start] = d[i][j]
					result[end] = d[i][r]
					r -= 1
					if len(s) + r == j:
						break
					start += 1
					end -= 1
				result[len(s) // 2] = d[i][r]
		for i in result:
			print(i + 1, end=' ')
		print()


for i in range(int(input())):
	stg = list(input())
	x = {}
	for i in range(len(stg)):
		if stg[i] not in x:
			x[stg[i]] = 1
		else:
			x[stg[i]] += 1
	count = 0
	for i in x:
		if x[i] % 2 == 1:
			count += 1
			if count == 2:
				break
	if count == 2:
		print('-1')
	else:
		m = dict()
		for i in range(len(stg)):
			if stg[i] in m:
				m[stg[i]].append(i + 1)
			else:
				m[stg[i]] = [i + 1]
		A = []
		for i in m:
			A.append(m[i])
		(x1, f) = ([], '')
		for i in range(len(A)):
			d0 = len(A[i]) // 2
			if d0 == 0:
				f = A[i][d0]
				continue
			a = [str(j) for j in A[i][0:d0]]
			z = ' '.join(a)
			x1.append(z)
			if len(A[i]) % 2 == 1:
				f = A[i][d0]
		if f != '':
			x1.append(f)
		for i in range(len(A) - 1, -1, -1):
			d0 = len(A[i]) // 2
			if len(A[i]) // 2 == 0:
				continue
			if len(A[i]) % 2 == 0:
				a = [str(j) for j in A[i][d0:len(A[i])]]
				z = ' '.join(a)
				x1.append(z)
			else:
				a = [str(j) for j in A[i][d0 + 1:len(A[i])]]
				z = ' '.join(a)
				x1.append(z)
		q = [str(i) for i in x1]
		z = ' '.join(q)
		print(z)


for _ in range(int(input())):
	s = input()
	d = {}
	for i in range(len(s)):
		if s[i] not in d:
			l = [i + 1]
			d.update({s[i]: l})
		else:
			d[s[i]].append(i + 1)
	o = 0
	l1 = [0] * len(s)
	start = 0
	end = len(s) - 1
	for i in d.keys():
		if len(d[i]) % 2 == 1:
			o += 1
	if o > 1:
		print(-1)
	else:
		for i in d.keys():
			x = len(d[i])
			c = 0
			if x % 2 == 0:
				while x != 0:
					l1[start] = d[i][c]
					start += 1
					c += 1
					l1[end] = d[i][c]
					end -= 1
					c += 1
					x -= 2
			else:
				l1[len(s) // 2] = d[i][c]
				c += 1
				x -= 1
				while x != 0:
					l1[start] = d[i][c]
					start += 1
					c += 1
					l1[end] = d[i][c]
					end -= 1
					c += 1
					x -= 2
		print(*l1)


n = int(input())
for t in range(0, n):
	s = input()
	d = dict()
	d1 = dict()
	for i in range(0, len(s)):
		if s[i] not in d:
			d[s[i]] = 1
			d1[s[i]] = [i + 1]
		else:
			d[s[i]] = d[s[i]] + 1
			d1[s[i]].append(i + 1)
	codd = 0
	x = 0
	for i in d.keys():
		y = d[i]
		if y % 2 == 1:
			codd = codd + 1
			x = i
	if codd > 1:
		print(-1)
	else:
		p = ''
		l = len(s)
		rl = l // 2
		if l % 2 == 1:
			rl = rl + 1
		for i in d.keys():
			y = d[i]
			p = p + i * (y // 2)
		s1 = p[::-1]
		if codd == 1:
			p = p + x
		p = p + s1
		f = []
		d2 = dict()
		for i in range(0, len(p)):
			if p[i] not in d2:
				d2[p[i]] = [i + 1]
			else:
				d2[p[i]].append(i + 1)
		for i in p:
			y = d1[i]
			f.append(y[-1])
			y.pop()
		print(*f)


for T in range(int(input())):
	s = input()
	N = len(s)
	setS = set(s)
	k = sorted(setS)
	c = {ch: list() for ch in k}
	for i in range(N):
		c[s[i]].append(i + 1)
	P = list()
	Podd = list()
	odd = 0
	for key in k:
		L = len(c[key])
		if L % 2 != 0:
			odd += 1
			Podd = c[key]
		else:
			P += c[key][:L // 2]
	k.reverse()
	P += Podd
	for key in k:
		L = len(c[key])
		if L % 2 == 0:
			P += c[key][L // 2:]
	if odd <= 1:
		print(*P)
	else:
		print(-1)


from collections import defaultdict
t = int(input())
for _ in range(t):
	hash = defaultdict(int)
	ho = defaultdict(list)
	s = input()
	n = len(s)
	for i in s:
		hash[i] += 1
	for i in range(n):
		ho[s[i]].append(i + 1)
	if n % 2 == 0:
		flag = 0
		ans = [-1] * n
		for i in hash.keys():
			if hash[i] % 2 != 0:
				flag = 1
				break
		if flag == 1:
			print(-1)
		else:
			i = 0
			la = list(hash.keys())
			a = 0
			b = n - 1
			while i < len(hash.keys()):
				k = la[i]
				x = 0
				for j in range(hash[k] // 2):
					(ans[a], ans[b]) = (ho[k][x], ho[k][x + 1])
					a += 1
					b -= 1
					x += 2
				i += 1
			print(*ans)
	else:
		ans = [-1] * n
		count = 0
		do = ''
		for i in hash.keys():
			if hash[i] % 2 != 0:
				do = i
				count += 1
		if count == 1:
			i = 0
			la = list(hash.keys())
			a = 0
			b = n - 1
			while i < len(hash.keys()):
				k = la[i]
				x = 0
				if k != do:
					for j in range(hash[k] // 2):
						(ans[a], ans[b]) = (ho[k][x], ho[k][x + 1])
						a += 1
						b -= 1
						x += 2
				i += 1
			x = 0
			for j in range(hash[do] // 2):
				(ans[a], ans[b]) = (ho[do][x], ho[do][x + 1])
				a += 1
				b -= 1
				x += 2
			ans[len(ans) // 2] = ho[do][x]
			print(*ans)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		try:
			d[s[i]] += [i + 1]
		except:
			d[s[i]] = [i + 1]
	k = 0
	for i in d.values():
		if len(i) % 2 != 0:
			k += 1
	if k > 1:
		print(-1)
	else:
		k = []
		c = []
		x = list(d.values())
		for i in x:
			if len(i) % 2 != 0:
				k = i.copy()
			else:
				c += i[:len(i) // 2]
		c += k.copy()
		x.reverse()
		for i in x:
			if len(i) % 2 != 0:
				continue
			else:
				c += i[len(i) // 2:]
		print(*c)


import collections

def find_all_indices(l, a):
	indices = []
	for i in range(len(l)):
		if l[i] == a:
			indices.append(i)
	return indices

def solve_for(s):
	freq = collections.Counter(s)
	(odd_parity_chars, even_parity_chars) = ([], [])
	for (c, c_count) in freq.items():
		if c_count % 2 == 0:
			even_parity_chars.append(find_all_indices(s, c))
		else:
			odd_parity_chars.append(find_all_indices(s, c))
	if len(odd_parity_chars) > 1:
		return '-1'
	(left, right, middle) = ([], [], [])
	for indices in even_parity_chars:
		even = True
		for i in indices:
			if even:
				left.append(str(i + 1))
			else:
				right.insert(0, str(i + 1))
			even = not even
	if len(odd_parity_chars) == 1:
		for i in odd_parity_chars[0]:
			middle.append(str(i + 1))
	return ' '.join(left + middle + right)
T = int(input())
for i in range(T):
	print(solve_for(input().strip()))


from collections import Counter
for _ in range(int(input())):
	s = input()
	n = len(s)
	res = [None] * n
	c = Counter(s)
	f = 1
	biksha = 0
	for i in c:
		if c[i] & 1:
			biksha += 1
		if biksha > 1:
			f = 0
			break
	if f == 0:
		print(-1)
	else:
		d = {}
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = [i + 1]
			else:
				d[s[i]].append(i + 1)
		ind = 0
		for i in range(0, 26):
			k = chr(i + 97)
			if c[k] > 0 and c[k] & 1:
				res[n // 2] = d[k].pop()
				c[k] -= 1
			if c[k] and c[k] % 2 == 0:
				while c[k]:
					res[ind] = d[k].pop()
					res[n - ind - 1] = d[k].pop()
					ind += 1
					c[k] -= 2
		print(*res, sep=' ')


n = int(input())
s = [input().strip() for _ in range(n)]
for astr in s:
	lfq = dict()
	for ltr in astr:
		if ltr in lfq:
			lfq[ltr] += 1
		else:
			lfq[ltr] = 1
	mid = ''
	tgt = []
	for (ltr, fq) in lfq.items():
		if fq % 2 == 1:
			mid = mid + ltr
		if fq > 1:
			tgt += [ltr] * (fq // 2)
	if len(mid) > 1:
		print(-1)
	else:
		if len(mid) == 1:
			tgt += [mid] + list(reversed(tgt))
		else:
			tgt += list(reversed(tgt))
		perm = [0] * len(tgt)
		floc = {ltr: 0 for ltr in lfq}
		for (p, ltr) in enumerate(astr):
			outp = tgt.index(ltr, floc[ltr])
			perm[outp] = p + 1
			floc[ltr] = outp + 1
		print(*perm)


for _ in range(int(input())):
	s = input()
	l1 = [e for e in range(1, len(s) + 1)]
	m = set(s)
	l = list(s)
	k = 0
	q = 0
	if len(m) == 1:
		print(*l1)
	else:
		for i in m:
			p = s.count(i)
			x = 0
			if s.count(i) % 2 != 0:
				k += 1
				x = 0
				x = l.index(i, x)
				x += 1
				l1[len(s) // 2] = x
				if s.count(i) > 1:
					p = s.count(i) - 1
				else:
					p = 0
			for e in range(0, p, 2):
				x = l.index(i, x)
				x += 1
				l1[q] = x
				x = l.index(i, x)
				x += 1
				l1[len(s) - q - 1] = x
				q += 1
		if k > 1:
			print(-1)
		else:
			print(*l1)


t = int(input())
for _ in range(t):
	s = input()
	count = False
	order = []
	a = sorted(set(s))
	temp = []
	for i in range(len(a)):
		temp.append([])
		for j in range(len(s)):
			if a[i] == s[j]:
				temp[i].append(j)
	for i in temp:
		if len(i) % 2 != 0:
			if count == True:
				order = [-2]
			count = True
	if order != [-2]:
		for i in temp:
			if len(i) % 2 == 0:
				for j in range(len(i)):
					if j % 2 == 0:
						order.insert(0, i[j])
					else:
						order.insert(len(order), i[j])
			else:
				for j in range(len(i) - 1):
					if j % 2 == 0:
						order.insert(0, i[j])
					else:
						order.insert(len(order), i[j])
				order.insert(int(len(order) / 2), i[len(i) - 1])
	for i in order:
		print(i + 1, '', end='')
	print()


def getidxfreq(string):
	arr = [[] for _ in range(26)]
	for (i, l) in enumerate(string):
		arr[ord(l) - 97].append(i)
	return arr
for n in range(int(input())):
	s = input()
	L = len(s)
	P = [None for _ in range(L)]
	arr = getidxfreq(s)
	countodd = sum([1 for x in arr if len(x) % 2 == 1])
	if countodd > 1:
		print('-1')
	else:
		(odd, k) = ('', 0)
		letters = [l for l in 'abcdefghijklmnopqrstuvwxyz' if len(arr[ord(l) - 97]) > 0]
		for l in letters:
			if len(arr[ord(l) - 97]) % 2 == 1:
				odd = l
			else:
				where = arr[ord(l) - 97]
				for i in range(0, len(arr[ord(l) - 97]), 2):
					P[k] = where[i]
					P[L - k - 1] = where[i + 1]
					k += 1
		if odd != '':
			where = arr[ord(odd) - 97]
			for w in where:
				P[k] = w
				k += 1
		print(' '.join([str(i + 1) for i in P]))


tt = int(input())
for a0 in range(tt):
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	t1 = 0
	t2 = 0
	for i in d:
		if d[i] & 1 and t1 == 1:
			t2 = -1
			break
		if d[i] & 1:
			t1 += 1
	if t2 == -1:
		print('-1')
		continue
	f = {}
	for i in range(len(s)):
		if s[i] in f:
			f[s[i]].append(i + 1)
		else:
			f[s[i]] = [i + 1]
	t1 = ''
	t2 = 1
	lh = []
	rh = []
	for (i, j) in f.items():
		l = len(j)
		if l & 1:
			t1 = j
			t2 = -1
			continue
		for i in range(l):
			if i & 1 == 1:
				lh.append(j[i])
			else:
				rh.insert(0, j[i])
	if t2 == -1:
		finalarr = lh + t1 + rh
	else:
		finalarr = lh + rh
	for i in finalarr:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	s = input()
	cnt = 0
	p = 0
	q = len(s) - 1
	ans = [0 for x in range(q + 1)]
	pos = 0
	v = [[] for i in range(26)]
	for i in range(len(s)):
		a = ord(s[i]) - 97
		v[a].append(i + 1)
	for i in range(26):
		if len(v[i]) % 2 == 1:
			cnt += 1
			pos = i
	if cnt > 1:
		print('-1')
		continue
	elif cnt == 1:
		for i in range(26):
			if len(v[i]) > 0 and len(v[i]) % 2 == 0:
				for j in range(0, len(v[i]), 2):
					ans[p] = v[i][j]
					p += 1
					ans[q] = v[i][j + 1]
					q -= 1
		for i in range(len(v[pos])):
			ans[p] = v[pos][i]
			p += 1
	else:
		for i in range(26):
			if len(v[i]) > 0:
				for j in range(0, len(v[i]), 2):
					ans[p] = v[i][j]
					p += 1
					ans[q] = v[i][j + 1]
					q -= 1
	for i in range(len(s)):
		print(ans[i], end=' ')
	print(end='\n')


from collections import Counter, defaultdict
for i in range(int(input())):
	words = input()
	word = Counter(words)
	wl = len(words)
	result = []
	oneOdd = 0
	notPalidrome = 0
	for i in word:
		if word[i] % 2 and oneOdd:
			notPalidrome = 1
			break
		if word[i] % 2:
			oneOdd = 1
	if notPalidrome:
		print('-1')
	else:
		d = defaultdict(list)
		for i in range(len(words)):
			d[words[i]].append(i + 1)
		right = ''
		left = ''
		middle = ' '
		for (k, v) in d.items():
			length = len(v)
			if length & 1:
				middle = ' ' + str(v[-1]) + ' '
				length -= 1
			left += '' + ' '.join(map(str, v[:length:2])) + ' '
			right = ' ' + ' '.join(map(str, v[1:length:2])) + right
		total = left.strip() + middle + right.strip()
		print(total.strip())


for _ in range(int(input())):
	s = input()
	s = list(s)
	l = sorted(list(set(s)))
	o = []
	c = 0
	p = ''
	for i in l:
		if s.count(i) % 2 != 0:
			c += 1
			p = i
	if c > 1:
		print('-1')
	elif c <= 1:
		if c == 1:
			l.remove(p)
		for q in range(len(s)):
			if p == s[q]:
				o.append(str(q + 1))
		for j in l:
			w = s.count(j)
			pa = 0
			crawl = 0
			for cr in range(len(s)):
				if j == s[cr] and crawl < w // 2:
					o.insert(pa, str(cr + 1))
					pa += 1
					crawl += 1
				elif j == s[cr] and w // 2 <= crawl < w:
					o.append(str(cr + 1))
		print(*o)


for test in range(int(input())):
	string = input()
	alpha = [[] for i in range(26)]
	for j in range(len(string)):
		a = ord(string[j]) - 97
		alpha[a].append(j + 1)
	(s1, s2, s3) = ([], [], [])
	(signal, sig) = (2, -1)
	for i in range(26):
		if len(alpha[i]) % 2 != 0:
			signal -= 1
			sig = i
		if signal == 0:
			break
	if signal == 0:
		print('-1')
		continue
	for i in range(26):
		if i != sig:
			s1 += alpha[i][:len(alpha[i]) // 2]
			s2 += alpha[i][len(alpha[i]) // 2:]
	if sig != -1:
		s3 = alpha[sig]
	s1 = s1 + s3 + s2[::-1]
	for k in s1:
		print(k, end=' ')
	print('')


q = int(input())
for qq in range(q):
	s = input()
	n = len(s)
	a = [(ord(s[i]) - ord('a'), i + 1) for i in range(n)]
	counts = [0] * 26
	for x in a:
		counts[x[0]] += 1
	odd = 0
	for i in range(26):
		if counts[i] % 2 == 1:
			odd += 1
	if odd > 1:
		print(-1)
		continue
	a.sort(key=lambda x: x[0])
	perm = [-1] * n
	i = 0
	while i < n:
		if i == n - 1:
			perm[i // 2] = a[i][1]
			break
		if a[i][0] != a[i + 1][0] and i % 2 == 0:
			tmp = a[i]
			a.pop(i)
			a.append(tmp)
			continue
		perm[i // 2] = a[i][1]
		perm[n - 1 - i // 2] = a[i + 1][1]
		i += 2
	for x in perm:
		print(x, end=' ')
	print('')


for i in range(int(input())):
	s = input()
	w = set(s)
	l = list(w)
	l.sort()
	o = []
	odd = 0
	p = ''
	u = 0
	for k in l:
		c = s.count(k)
		if c % 2 != 0:
			odd = odd + 1
			p = k
	if odd > 1:
		print(-1)
	elif odd == 0 or odd == 1:
		if odd == 1:
			l.remove(p)
		for q in range(len(s)):
			if p == s[q]:
				o.append(str(q + 1))
		for q in l:
			e = s.count(q)
			y = 0
			u = 0
			for r in range(len(s)):
				if q == s[r] and u < e // 2:
					o.insert(y, str(r + 1))
					u = u + 1
					y = y + 1
				elif q == s[r] and e // 2 <= u < e:
					o.append(str(r + 1))
		print(' '.join(o))


t = int(input())
while t:
	st = input()
	alp = []
	n = len(st)
	ans = [0] * n
	mid = n // 2
	alph = 'abcdefghijklmnopqrstuvwxyz'
	for p in alph:
		arr2 = []
		for i in range(n):
			if p == st[i]:
				arr2.append(i + 1)
		alp.append(arr2)
	odd = 0
	m = 0
	for i in range(26):
		if len(alp[i]) % 2 != 0:
			odd += 1
			m = i
			if odd > 1:
				break
	if odd > 1:
		print('-1')
	else:
		if odd == 1:
			ans[mid] = alp[m][0]
			alp[m].pop(0)
		j = 0
		flag = 0
		ind = 0
		te = list()
		for y in alp:
			if len(y) != 0 and j <= n // 2:
				temp = len(y)
				for i in range(temp // 2):
					ans[j] = y[i]
					ind = j
					j += 1
					ans[n - 1 - ind] = y[temp - 1 - i]
		for z in ans:
			print(z, end=' ')
		print()
	t -= 1


testcases = int(input())
for q in range(testcases):
	input_string = input()
	alphabet = {}
	alphabet_order = []
	final_string = []
	for i in range(0, len(input_string)):
		try:
			alphabet[input_string[i]].append(i + 1)
		except:
			alphabet[input_string[i]] = []
			alphabet_order.append(input_string[i])
			alphabet[input_string[i]].append(i + 1)
	odd_index = list()
	for (key, value) in alphabet.items():
		if len(value) % 2 == 1:
			odd_index.append(key)
	if len(odd_index) > 1:
		print('-1')
		continue
	elif len(odd_index) == 1:
		for i in alphabet_order:
			if len(alphabet.get(i)) % 2 == 1:
				continue
			half_len = int(len(alphabet.get(i)) / 2)
			for j in range(0, half_len):
				final_string.append(alphabet.get(i).pop(j))
		for i in range(0, len(alphabet.get(odd_index[0]))):
			final_string.append(alphabet.get(odd_index[0])[i])
		alphabet_order.pop(alphabet_order.index(odd_index[0]))
		for i in reversed(alphabet_order):
			for j in range(0, len(alphabet.get(i))):
				final_string.append(alphabet.get(i)[j])
		print(' '.join([str(x) for x in final_string]))
	else:
		for i in alphabet_order:
			half_len = int(len(alphabet.get(i)) / 2)
			for j in range(0, half_len):
				final_string.append(alphabet.get(i).pop(j))
		for i in reversed(alphabet_order):
			for j in range(0, len(alphabet.get(i))):
				final_string.append(alphabet.get(i)[j])
		print(' '.join([str(x) for x in final_string]))


from collections import Counter, defaultdict
t = int(input())
while t > 0:
	s = input()
	c = Counter(s)
	temp = [count for count in c.values() if count % 2 == 1]
	if len(temp) <= 1:
		freq = defaultdict(list)
		for (idx, char) in enumerate(s):
			freq[char].append(idx + 1)
		leftPart = ''
		middlePart = ' '
		rightPart = ''
		for (k, v) in freq.items():
			length = len(v)
			if len(v) % 2 == 1:
				middlePart = ' ' + str(v[-1]) + ' '
				length -= 1
			leftPart += ' ' + ' '.join(map(str, v[:length:2]))
			rightPart = ' '.join(map(str, v[1:length:2])) + ' ' + rightPart
		answer = leftPart.strip() + middlePart + rightPart.strip()
		print(answer.strip())
	else:
		print('-1')
	t -= 1


for k in range(int(input())):
	s = list(input())
	l = list(set(s))
	l.sort()
	n = len(l)
	t = []
	mark = 2
	flag = 0
	pos = 0
	chk = -1
	for i in range(n):
		total_alpha = 0
		for j in range(len(s)):
			if l[i] == s[j]:
				if mark == 2:
					pos = i
					t.insert(len(t) // 2, j + 1)
				total_alpha = total_alpha + 1
		if total_alpha % 2 != 0:
			mark = mark - 1
			chk = pos
		if mark == 0:
			flag = 1
			break
	if flag == 0 and chk != -1:
		for i in range(chk + 1, n):
			cnt = s.count(l[i])
			pointer = 1
			for j in range(len(s)):
				if l[i] == s[j] and pointer <= cnt // 2:
					t.insert(0, j + 1)
					pointer = pointer + 1
				elif l[i] == s[j] and pointer > cnt // 2:
					t.insert(len(t), j + 1)
					pointer = pointer + 1
	if flag == 1:
		print('-1')
	else:
		string = ' '.join(map(str, t))
		print(string)


test = int(input())
for tt in range(test):
	text = input()
	data = {}
	data_len = len(text)
	ans = [0] * data_len
	i = 1
	for c in text:
		if c not in data:
			data[c] = []
		data[c].append(i)
		i += 1
	odd_chars = 0
	the_final_index = 0
	the_odd_key = -1
	the_length = data_len - 1
	for (key, value) in data.items():
		if len(value) & 1:
			the_odd_key = key
			odd_chars += 1
	if odd_chars >= 2:
		print('-1')
	else:
		if the_odd_key != -1:
			ans[data_len // 2] = data[the_odd_key].pop()
		for (key, value) in data.items():
			temp = 0
			for item in value:
				if temp & 1:
					ans[the_final_index] = item
					the_final_index += 1
				else:
					ans[the_length - the_final_index] = item
				temp += 1
		print(*ans)


from collections import deque
str = 'abcdefghijklmnopqrstuvwxyz'
for i in range(int(input())):
	x = input()
	ls = deque()
	odd = 0
	con = []
	z = -1
	flag = 0
	if len(x) == 1:
		print('1')
	else:
		for k in str:
			y = x.count(k)
			if y % 2:
				odd = odd + 1
				z = k
			con.append(y)
		if odd > 1:
			flag = 1
		else:
			if z != -1:
				m = ord(z) - 97
				e = x.find(chr(m + 97))
				ls.append(e + 1)
				con[m] -= 1
				while con[m] > 0:
					e = x.find(chr(m + 97), e + 1)
					ls.append(e + 1)
					e = x.find(chr(m + 97), e + 1)
					ls.append(e + 1)
					con[m] -= 2
			for l in x:
				m = ord(l) - 97
				if con[m] % 2 == 0 and con[m] > 1:
					f = 0
					while con[m] > 0:
						e = x.find(chr(m + 97), f)
						ls.appendleft(e + 1)
						e = x.find(chr(m + 97), e + 1)
						ls.append(e + 1)
						f = e + 1
						con[m] -= 2
		if flag:
			print('-1')
		else:
			for do in range(len(ls) - 1):
				print(ls[do], end=' ')
			print(ls[do + 1])


from collections import Counter
for _ in range(int(input())):
	s = str(input())
	fs = s
	t = 26
	L = []
	odd = []
	ev = []
	S = [0] * len(s)
	while t:
		L.append(0)
		t = t - 1
	if sum((v % 2 for v in Counter(s).values())) <= 1:
		for i in s:
			L[ord(i) - ord('a')] += 1
		for i in L:
			k = i
			g = L.index(i)
			chi = chr(g + 97)
			L[g] = -1
			chi = str(chi)
			if k % 2 == 0:
				while k:
					ev.append(chi)
					k -= 1
			else:
				while k:
					odd.append(chi)
					k -= 1
		if len(s) % 2 != 0:
			S[(len(s) - 1) // 2] = odd[0]
			st = (len(s) - 1) // 2 - 1
			ed = (len(s) - 1) // 2 + 1
			tt = len(odd) - 1
			ee = len(ev)
			co = 0
			while tt:
				tt -= 2
				S[st] = odd[0]
				S[ed] = odd[0]
				st -= 1
				ed += 1
			while ee:
				ee -= 2
				S[st] = ev[co]
				co += 1
				S[ed] = ev[co]
				co += 1
				st -= 1
				ed += 1
		else:
			st = len(s) // 2 - 1
			ed = st + 1
			ee = len(ev)
			co = 0
			while ee:
				ee -= 2
				S[st] = ev[co]
				co += 1
				S[ed] = ev[co]
				co += 1
				st -= 1
				ed += 1
		ans = []
		fS = S
		for ii in fS:
			A = fs.index(ii)
			ans.append(A + 1)
			fs = fs.replace(ii, 'Z', 1)
		print(*ans)
	else:
		print(-1)


t = int(input())
for r in range(t):
	st = list(input().strip())
	pal = {}
	for i in range(len(st)):
		if st[i] in pal:
			pal[st[i]].append(str(i + 1))
		else:
			pal[st[i]] = [str(i + 1)]
	v = sorted(pal.items(), key=lambda x: len(x[1]), reverse=True)
	(o, e) = ([], [])
	for k in range(len(v)):
		if len(v[k][1]) % 2:
			o.append(v[k][1])
		else:
			e.append(v[k][1])
	if len(o) > 1:
		print('-1')
	elif len(e) != 0:
		st = list(e[0])
		for i in range(1, len(e)):
			l = len(st)
			st[l // 2:l // 2] = e[i]
		if len(o) == 1:
			l = len(st)
			st[l // 2:l // 2] = o[0]
		print(' '.join(st))
	else:
		print(' '.join(o[0]))


from collections import defaultdict

def solve():
	t = int(input())
	for z in range(t):
		a = input().strip()
		charArr = defaultdict(list)
		for i in range(len(a)):
			charArr[a[i]].append(i)
		oddChars = 0
		oddChar = ''
		for i in charArr.keys():
			charArr[i].sort()
			if len(charArr[i]) % 2 != 0:
				oddChars += 1
				oddChar = i
		if oddChars > len(a) % 2:
			print(-1)
			continue
		pos = [-1] * len(a)
		ptr = 0
		keyList = list(charArr.keys())
		keyList.sort()
		while ptr < len(a) // 2:
			for i in keyList:
				for j in range(len(charArr[i]) // 2):
					pos[charArr[i][j]] = ptr + 1
					pos[charArr[i][0 - j - 1]] = len(a) - ptr
					ptr += 1
		if oddChars:
			pos[charArr[oddChar][(len(charArr[oddChar]) - 1) // 2]] = ptr + 1
		ans = [0] * len(a)
		for i in range(len(a)):
			ans[pos[i] - 1] = i + 1
		print(' '.join([str(i) for i in ans]))
solve()


from collections import defaultdict
t = int(input())
for k in range(t):
	s = input()
	freq = defaultdict(int)
	for letter in s:
		freq[letter] += 1
	odd = 0
	for item in freq.values():
		if item % 2 == 1:
			odd += 1
	if odd == 1 and len(s) % 2 == 1 or (odd == 0 and len(s) % 2 == 0):
		arr = defaultdict(list)
		for (i, value) in enumerate(s):
			arr[value].append(i)
		alpha = 'abcdefghijklmnopqrstuvwxyz'
		t = ''
		oddletter = ''
		for letter in alpha:
			if freq[letter] % 2 == 1:
				oddletter = letter
			if freq[letter] != 0:
				t += letter * int(freq[letter] / 2)
		T = t
		if len(oddletter) > 0:
			T += oddletter
		T += t[::-1]
		ans = ''
		for letter in T:
			ans += str(arr[letter].pop(0) + 1) + ' '
		print(ans)
	else:
		print('-1')