Chef has N strings. Each string S_{i} has length M and consists only of lowercase english letters.

Chef likes [palindromes], and would like each S_{i} to be a palindrome. To achieve this, he can perform the following move:
Pick an index i such that 1 ≤ i < N and an index j such that 1 ≤ j ≤ M.
Then, swap the j^{th} character of string S_{i} with the j^{th} character of string S_{i+1}.

Informally, Chef can swap the j^{th} character of any two consecutive strings.

Find the minimum number of moves required to make every string a palindrome. Print -1 if it is not possible to achieve this.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and M, denoting the number of strings and their length, respectively.
- The i^{th} of the next N lines contains the string S_{i}.

------ Output Format ------ 

- Print a single integer on a new line as the answer to each test case: the minimum number of swaps needed to make every S_{i} a palindrome, or -1 if this is not possible.

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

$1 ≤ T ≤ 5\cdot 10^{5}$
$1 ≤ N, M ≤ 5 \cdot 10^{5}$
- Each $S_{i}$ contains only lowercase english letters.
- The sum of $N\times M$ across all test cases won't exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3 2
ac
ba
cb
2 3
xkx
ptp
4 4
abaa
baba
baab
aabb
4 4
abaa
baba
baab
aaab

----- Sample Output 1 ------ 
2
0
-1
3

----- explanation 1 ------ 
Test case $1$: Chef can make all the strings palindromes in two operations:
- First, swap the second characters of $S_{1}$ and $S_{2}$. Now, the strings are $\{\texttt{aa, bc, cb}\}$
- Then, swap the first characters of $S_{2}$ and $S_{3}$. Now, the strings are $\{\texttt{aa, bb, cc} \}$, which are all palindromes.

Test case $2$: Both strings are already palindromes.

Test case $3$: It can be shown that it's impossible to make all $4$ strings simultaneously palindromes.

Test case $4$: One optimal sequence of operations is as follows:
- Swap the first characters of $S_{3}$ and $S_{4}$. Now, the strings are $\{\texttt{abaa, baba, aaab, baab} \}$.
- Swap the second characters of $S_{1}$ and $S_{2}$. Now, the strings are $\{\texttt{aaaa, bbba, aaab, baab} \}$.
- Swap the fourth characters of $S_{2}$ and $S_{3}$. Now, the strings are $\{\texttt{aaaa, bbbb, aaaa, baab} \}$.

Thus, the final strings are all palindromes. It can be proven that we cannot achieve all palindromes in less than $3$ moves.

Source: codechef | Difficulty: VERY_HARD
Tags: String algorithms

Sorting

Range queries

Segment trees revisited

Data structures


Solutions:
from sys import stdin
input = stdin.readline
from queue import Queue
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

class FenwickTree:

	def __init__(self, x):
		bit = self.bit = list(x)
		size = self.size = len(bit)
		for i in range(size):
			j = i | i + 1
			if j < size:
				bit[j] += bit[i]

	def update(self, idx, x):
		while idx < self.size:
			self.bit[idx] += x
			idx |= idx + 1

	def __call__(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def find_kth(self, k):
		idx = -1
		for d in reversed(range(self.size.bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < self.size and self.bit[right_idx] <= k:
				idx = right_idx
				k -= self.bit[idx]
		return (idx + 1, k)
block_size = 700

class SortedList:

	def __init__(self):
		self.macro = []
		self.micros = [[]]
		self.micro_size = [0]
		self.fenwick = FenwickTree([0])
		self.size = 0

	def insert(self, x):
		i = lower_bound(self.macro, x)
		j = upper_bound(self.micros[i], x)
		self.micros[i].insert(j, x)
		self.size += 1
		self.micro_size[i] += 1
		self.fenwick.update(i, 1)
		if len(self.micros[i]) >= block_size:
			self.micros[i:i + 1] = (self.micros[i][:block_size >> 1], self.micros[i][block_size >> 1:])
			self.micro_size[i:i + 1] = (block_size >> 1, block_size >> 1)
			self.fenwick = FenwickTree(self.micro_size)
			self.macro.insert(i, self.micros[i + 1][0])

	def pop(self, k=0):
		(i, j) = self._find_kth(k)
		self.size -= 1
		self.micro_size[i] -= 1
		self.fenwick.update(i, -1)
		return self.micros[i].pop(j)

	def __getitem__(self, k):
		(i, j) = self._find_kth(k)
		return self.micros[i][j]

	def __contains__(self, x):
		i = lower_bound(self.macro, x)
		j = lower_bound(self.micros[i], x)
		(i, j) = (i, j) if j < self.micro_size[i] else (i + 1, 0)
		return i < len(self.micros) and j < self.micros_size[i] and (self.micros[i][j] == x)

	def lower_bound(self, x):
		i = lower_bound(self.macro, x)
		return self.fenwick(i) + lower_bound(self.micros[i], x)

	def upper_bound(self, x):
		i = upper_bound(self.macro, x)
		return self.fenwick(i) + upper_bound(self.micros[i], x)

	def _find_kth(self, k):
		return self.fenwick.find_kth(k + self.size if k < 0 else k)

	def __len__(self):
		return self.size

	def __iter__(self):
		return (x for micro in self.micros for x in micro)

	def __repr__(self):
		return str(list(self))

	def count(self, x):
		return self.upper_bound(x) - self.lower_bound(x)

def helper(s1, s2):
	a = list(s1)
	b = list(s2)
	a.sort()
	b.sort()
	if a == b:
		d1 = {}
		d2 = {}
		v1 = [0] * len(s1)
		v2 = [0] * len(s2)
		for i in range(len(s1)):
			if s1[i] not in d1:
				d1[s1[i]] = Queue()
			d1[s1[i]].put(i)
			if s2[i] not in d2:
				d2[s2[i]] = Queue()
			d2[s2[i]].put(i)
		c = SortedList()
		d = SortedList()
		curr = 0
		i = 0
		j = 0
		cc = 0
		while i < len(s1) and j < len(s2):
			e = d2[s1[i]].queue[0]
			f = len(d) - d.upper_bound(e)
			g = d1[s2[j]].queue[0]
			h = len(c) - c.upper_bound(g)
			if e + f - i <= g + h - j:
				d.insert(e)
				d2[s1[i]].get()
				d1[s1[i]].get()
				curr += e + f - cc
				v2[e] = 1
				i += 1
			else:
				c.insert(g)
				d1[s2[j]].get()
				d2[s2[j]].get()
				curr += g + h - cc
				v1[g] = 1
				j += 1
			cc += 1
			while i < len(s1) and v1[i] == 1:
				i += 1
			while j < len(s2) and v2[j] == 1:
				j += 1
		return curr
	else:
		return -1
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		s = input().strip()
		a.append(s)
	ans = 0
	p = 1
	for i in range(m // 2):
		s1 = ''
		s2 = ''
		for j in range(n):
			s1 += a[j][i]
			s2 += a[j][m - i - 1]
		cu = helper(s1, s2)
		if cu == -1:
			p = 0
			break
		else:
			ans += cu
	if p:
		print(ans)
	else:
		print(-1)


from collections import defaultdict

def chk(s, t):
	h = defaultdict(list)
	pos = []
	for i in range(len(s)):
		h[s[i]].append(i)
	for i in range(len(t)):
		if t[i] not in h or len(h[t[i]]) == 0:
			return -1
		pos.append(h[t[i]][0])
		h[t[i]].pop(0)
	return pos

def mergesort(arr):
	length = len(arr)
	count = 0
	if length > 1:
		(left, right) = (0, length)
		mid = left + (right - left) // 2
		(leftarray, a) = mergesort(arr[left:mid])
		(rightarray, b) = mergesort(arr[mid:right])
		count += a + b
		(i, j, k) = (0, 0, 0)
		while i < len(leftarray) and j < len(rightarray):
			if leftarray[i] <= rightarray[j]:
				arr[k] = leftarray[i]
				i += 1
			else:
				arr[k] = rightarray[j]
				count += len(leftarray) - i
				j += 1
			k += 1
		while i < len(leftarray):
			arr[k] = leftarray[i]
			k += 1
			i += 1
		while j < len(rightarray):
			arr[k] = rightarray[j]
			k += 1
			j += 1
	return (arr, count)
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split(' '))
	arr = []
	for l in range(N):
		arr.append(list(input()))
	res = 0
	chek = False
	for j in range(M // 2):
		(s, t) = ('', '')
		for i in range(N):
			s += arr[i][j]
			t += arr[i][M - j - 1]
		pos = chk(s, t)
		if pos == -1:
			print(-1)
			chek = True
			break
		res += mergesort(pos)[1]
	if not chek:
		print(res)