We had a string s consisting of n lowercase Latin letters. We made k copies of this string, thus obtaining k identical strings s_1, s_2, ..., s_{k}. After that, in each of these strings we swapped exactly two characters (the characters we swapped could be identical, but they had different indices in the string).

You are given k strings s_1, s_2, ..., s_{k}, and you have to restore any string s so that it is possible to obtain these strings by performing aforementioned operations. Note that the total length of the strings you are given doesn't exceed 5000 (that is, k·n ≤ 5000).


-----Input-----

The first line contains two integers k and n (1 ≤ k ≤ 2500, 2 ≤ n ≤ 5000, k · n ≤ 5000) — the number of strings we obtained, and the length of each of these strings.

Next k lines contain the strings s_1, s_2, ..., s_{k}, each consisting of exactly n lowercase Latin letters.


-----Output-----

Print any suitable string s, or -1 if such string doesn't exist.


-----Examples-----
Input
3 4
abac
caab
acba

Output
acab

Input
3 4
kbbu
kbub
ubkb

Output
kbub

Input
5 4
abcd
dcba
acbd
dbca
zzzz

Output
-1



-----Note-----

In the first example s_1 is obtained by swapping the second and the fourth character in acab, s_2 is obtained by swapping the first and the second character, and to get s_3, we swap the third and the fourth character.

In the second example s_1 is obtained by swapping the third and the fourth character in kbub, s_2 — by swapping the second and the fourth, and s_3 — by swapping the first and the third.

In the third example it's impossible to obtain given strings by aforementioned operations.

Difficulty: HARD
Tags: String algorithms

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
read = lambda : list(map(int, input().split()))
from collections import Counter as co
(k, n) = read()
s = input()
repeated = len(s) != len(set(s))
etalon = co(s)
a = []
kk = []
ap = a.append
for i in range(k - 1):
	ap(input())
	if co(a[-1]) != etalon:
		print(-1)
		return
ss = False
for i in a:
	if i != s:
		ss = i
		for j in range(len(s)):
			if s[j] != ss[j]:
				kk.append(j)
		break
if len(kk) > 4:
	print(-1)
	return
if ss:
	if repeated:
		for i in a:
			k = 0
			for j in range(len(i)):
				if s[j] != i[j]:
					k += 1
			if k != 0 and k != 2:
				break
		else:
			print(s)
			return
	if len(kk) != 2:
		for i in range(len(kk)):
			for j in range(i):
				stry = s[:kk[j]] + s[kk[i]] + s[kk[j] + 1:kk[i]] + s[kk[j]] + s[kk[i] + 1:]
				for u in a:
					k = 0
					for j in range(len(u)):
						if stry[j] != u[j]:
							k += 1
					if not (k == 0 and repeated) and k != 2:
						break
				else:
					print(stry)
					return
	if len(kk) == 2:
		for change in kk:
			for i in range(len(s)):
				if change == i:
					continue
				if i > change:
					stry = s[:change] + s[i] + s[change + 1:i] + s[change] + s[i + 1:]
				else:
					stry = s[:i] + s[change] + s[i + 1:change] + s[i] + s[change + 1:]
				for u in a:
					k = 0
					for j in range(len(u)):
						if stry[j] != u[j]:
							k += 1
					if not (k == 0 and repeated) and k != 2:
						break
				else:
					print(stry)
					return
	print(-1)
else:
	if repeated:
		print(s)
		return
	print(s[1] + s[0] + s[2:])


(n, k) = map(int, input().split())
nn = []
ans = ''
for i in range(n):
	mid = input()
	if mid in nn:
		ans = mid
		continue
	nn.append(mid)
	n = len(nn)
if len(nn) == 1:
	ans = nn[0]
	ans = list(ans)
	(ans[0], ans[1]) = (ans[1], ans[0])
	print(''.join(ans))
else:
	diff = []
	check = True
	cnt = {chr(97 + i): 0 for i in range(26)}
	for v in range(k):
		cnt[nn[0][v]] += 1
	for i in range(n):
		cnt2 = {chr(97 + i): 0 for i in range(26)}
		for j in range(k):
			cnt2[nn[i][j]] += 1
		if cnt != cnt2:
			print('-1')
			check = False
			break
	if check:
		check = False
		for i in range(n):
			check = False
			for j in range(i, n):
				diff = [l for l in range(k) if nn[i][l] != nn[j][l]]
				if len(diff) > 4:
					check = True
					print('-1')
					break
			if check:
				break
		diff = [l for l in range(k) if nn[0][l] != nn[1][l]]
		mid = []
		check2 = False
		for i in range(k):
			if nn[0][i] in mid:
				check2 = True
				break
			mid.append(nn[0][i])
		if not check:
			res = list(nn[0])
			check = False
			for i in range(len(diff)):
				if check:
					break
				for j in range(k):
					if i == j:
						continue
					(res[diff[i]], res[j]) = (res[j], res[diff[i]])
					ans = ''.join(res)
					check = True
					for x in range(n):
						mid = [ans[y] for y in range(k) if nn[x][y] != ans[y]]
						if len(mid) == 2:
							continue
						elif len(mid) == 0 and check2:
							continue
						else:
							check = False
					if check:
						print(ans)
						check = True
						break
					(res[diff[i]], res[j]) = (res[j], res[diff[i]])
			if not check:
				print('-1')


import sys
(k, n) = map(int, input().split())
s = [list(word.rstrip()) for word in sys.stdin]
double = True if max((s[0].count(chr(i + 97)) for i in range(26))) > 1 else False
diff = [set() for _ in range(k)]
diff_cnt = [0] * k
for i in range(1, k):
	for j in range(n):
		if s[0][j] != s[i][j]:
			diff[i].add(j)
			diff_cnt[i] += 1
			if diff_cnt[i] > 4:
				print(-1)
				exit()
for i in range(n):
	for j in range(i + 1, n):
		(s[0][i], s[0][j]) = (s[0][j], s[0][i])
		for x in range(1, k):
			w = [y for y in diff[x] | {i, j} if s[0][y] != s[x][y]]
			if double and len(w) == 0:
				continue
			if len(w) == 2 and s[0][w[0]] == s[x][w[1]] and (s[0][w[1]] == s[x][w[0]]):
				continue
			break
		else:
			print(''.join(s[0]))
			exit()
		(s[0][i], s[0][j]) = (s[0][j], s[0][i])
print(-1)


import collections

def swapCharacters(strings, k, n):
	if k == 1:
		s0 = list(strings[0])
		(s0[0], s0[1]) = (s0[1], s0[0])
		return ''.join(s0)
	freq = collections.Counter(strings[0])
	canSame = max(freq.values()) >= 2
	for s in strings:
		if collections.Counter(s) != freq:
			return -1
	max_dist = 0
	max_dist_s = None
	s0 = strings[0]
	for s1 in strings[1:]:
		dist = HammingDistance(s0, s1, n)
		if dist > max_dist:
			max_dist = dist
			max_dist_s = s1
	if max_dist > 4:
		return -1
	diffs = [i for i in range(n) if s0[i] != s1[i]]
	s0 = list(s0)
	for i in diffs:
		for j in range(n):
			(s0[i], s0[j]) = (s0[j], s0[i])
			dist = HammingDistance(s0, s1, n)
			if dist == 2 or (dist == 0 and canSame):
				cand = ''.join(s0)
				if verifyAll(strings, k, n, cand, canSame):
					return cand
			(s0[i], s0[j]) = (s0[j], s0[i])
	return -1

def HammingDistance(s0, s1, n):
	count = 0
	for i in range(n):
		if s0[i] != s1[i]:
			count += 1
	return count

def verifyAll(strings, k, n, cand, canSame):
	for s in strings:
		dist = HammingDistance(s, cand, n)
		if (dist != 0 or not canSame) and dist != 2:
			return False
	return True
(k, n) = [int(x) for x in input().split()]
strings = set()
for _ in range(k):
	strings.add(input())
strings = list(strings)
k = len(strings)
res = swapCharacters(strings, k, n)
print(res)