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: interview

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:]
                #print(stry)
                for u in a:
                    k = 0
                    for j in range(len(u)):
                        if stry[j] != u[j]: k += 1
                    #print(stry,i,k)
                    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
                    #print(stry,i,k)
                    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:])


def solve():
    read=lambda:list(map(int,input().split()))
    from collections import Counter as co
    k,n=read()
    s=list(input())
    repeated=(len(s)!=len(set(s)))
    etalon=co(s)
    a=[]
    kk=[]
    ap=a.append
    
    for i in range(k-1):
        ap(list(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(''.join(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(''.join(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(''.join(stry))
                        return
        print(-1)
    
    else:
        if repeated:
            print(''.join(s))
            return
        print(s[1]+s[0]+''.join(s[2:]))
solve()

#!/usr/bin/env python3

n,k = list(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])
        #print(diff)
        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)
                    #print(ans)
                    check = True
                    for x in range(n):
                        mid = [ans[y] for y in range(k) if nn[x][y] != ans[y]]
                        #print(len(diff))
                        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 = list(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)
                return

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]))
            return
        s[0][i], s[0][j] = s[0][j], s[0][i]

print(-1)