A substring of some string is called the most frequent, if the number of its occurrences is not less than number of occurrences of any other substring.

You are given a set of strings. A string (not necessarily from this set) is called good if all elements of the set are the most frequent substrings of this string. Restore the non-empty good string with minimum length. If several such strings exist, restore lexicographically minimum string. If there are no good strings, print "NO" (without quotes).

A substring of a string is a contiguous subsequence of letters in the string. For example, "ab", "c", "abc" are substrings of string "abc", while "ac" is not a substring of that string.

The number of occurrences of a substring in a string is the number of starting positions in the string where the substring occurs. These occurrences could overlap.

String a is lexicographically smaller than string b, if a is a prefix of b, or a has a smaller letter at the first position where a and b differ.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of strings in the set.

Each of the next n lines contains a non-empty string consisting of lowercase English letters. It is guaranteed that the strings are distinct.

The total length of the strings doesn't exceed 10^5.


-----Output-----

Print the non-empty good string with minimum length. If several good strings exist, print lexicographically minimum among them. Print "NO" (without quotes) if there are no good strings.


-----Examples-----
Input
4
mail
ai
lru
cf

Output
cfmailru

Input
3
kek
preceq
cheburek

Output
NO



-----Note-----

One can show that in the first sample only two good strings with minimum length exist: "cfmailru" and "mailrucf". The first string is lexicographically minimum.

Difficulty: interview

Starter code:

Solutions:
n = int(input())

wrong_str = False

strings = []
sets = []
for _ in range(n):
    new_string = input()
    new_string_set = set(new_string)
    if len(new_string) != len(new_string_set):
        wrong_str = True
        break

    strings.append(new_string)
    sets.append(new_string_set)

if wrong_str:
    print("NO")
    return


connections = []
for _ in range(n):
    connections.append((-1,-1))

changed = True

while changed:

    changed = False

    for i in range(len(strings)):

        if strings[i] == None:
            continue

        for j in range(i + 1, len(strings)):

            if strings[j] == None:
                continue

            if len(set(strings[i]).intersection(set(strings[j]))) == 0:
                continue

            a = strings[i]
            b = strings[j]

            #print(a, b)

            if b in a:
                strings[j] = None
                changed = True
            elif a in b:
                strings[i] = b
                strings[j] = None
                changed = True
            else:

                is_ok = False

                start_index = a.find(b[0])
                if start_index != -1 and a[start_index:] in b:
                    strings[i] += strings[j][len(a) - start_index:]
                    strings[j] = None
                    is_ok = True
                    changed = True

                if not is_ok:
                    start_index = b.find(a[0])
                    if start_index != -1 and  b[start_index:] in a:
                        strings[i] = strings[j] + strings[i][len(b) - start_index:]
                        strings[j] = None
                        is_ok = True
                        changed = True

                if not is_ok:
                    print("NO")
                    return




        if wrong_str:
            print("NO")
            return

    strings = [x for x in strings if x is not None]

whole_str = "".join(strings)

if len(whole_str) != len(set(whole_str)):
    print("NO")
    return

print("".join(sorted(strings)))





n = int(input())
A = []
for i in range (0,n):
    A = A + [input()]
start = [100]*26
end = [100]*26
def num(x):
    return(ord(x)-ord("a"))
def let(x):
    return(chr(x+ord("a")))
def ans(x):
    final = []
    for i in range (0,n):
        B = list(A[i])
        if len(B) == 1:
            if start[num(B[0])] == 100:
                start[num(B[0])] = -100
            if end[num(B[0])] == 100:
                end[num(B[0])] = -100
        else:
            for j in range (0,len(B)):
                if j==0:
                    if start[num(B[j])] == 100 or start[num(B[j])] == -100:
                        start[num(B[j])] = -100
                    if end[num(B[j])] == 100 or end[num(B[j])] == -100:
                        end[num(B[j])] = num(B[j+1])
                    elif end[num(B[j])] == num(B[j+1]): g=0
                    else:
                        return("NO")
                elif 0<j<len(B)-1:
                    if start[num(B[j])] == 100 or start[num(B[j])] == -100:
                        start[num(B[j])] = num(B[j-1])
                    elif start[num(B[j])] != num(B[j-1]):
                        return("NO")
                    if end[num(B[j])] == 100 or end[num(B[j])] == -100:
                        end[num(B[j])] = num(B[j+1])
                    elif end[num(B[j])] != num(B[j+1]):
                        return("NO")
                elif j == len(B)-1:
                    if end[num(B[j])] == 100:
                        end[num(B[j])] = -100
                    if start[num(B[j])] == 100 or start[num(B[j])] == -100:
                        start[num(B[j])] = num(B[j-1])
                    elif start[num(B[j])] == num(B[j-1]): g=0
                    else:
                        return("NO")
    if len(set(start))+max(0,start.count(100)-1)+max(0,start.count(-100)-1) != 26:
            return("NO")
    elif len(set(end))+max(0,end.count(100)-1)+max(0,end.count(-100)-1) != 26:
            return("NO")
    else:
        for i in range (0,26):
            if start[i] != -100:
                g=0
            else:
                final = final + [let(i)]
                j = end[i]
                while j != -100:
                    final = final + [let(j)]
                    j = end[j]
        if len(final) != len(set(start))-min(1,start.count(100))+max(0,start.count(-100)-1):
            return("NO")
        else:
            return("".join(final))
print(ans(A))

n=int(input())
m=[]
sc=[]
for i in range(n):
    m.append(input())
    sc.append(set(m[i]))
    if len(sc[i])!=len(m[i]):
        print('NO')
        break
else:
    i=0
    pX=False
    while i<len(m):
        j=i+1
        p=False
        while j<len(m):
            #print(m)
            z=len(sc[i].intersection(sc[j]))
            #a=len(sc[i])
            #b=len(sc[j])
            if m[i] in m[j]:
                m[i]=m[j]
                sc[i]=sc[j]
                sc.pop(j)
                m.pop(j)
                p=True
                break
            elif m[j] in m[i]:
                sc.pop(j)
                m.pop(j)
                j-=1
            elif z>0:
                if m[i][-z:]==m[j][:z]:
                    m[i]+=m[j][z:]
                elif m[j][-z:]==m[i][:z]:
                    m[i]=m[j]+m[i][z:]
                else:
                    pX=True
                    break
                sc[i]=set(m[i])
                m.pop(j)
                sc.pop(j)
                j-=1
                p=True
            j+=1
        if not p:
            i+=1
        if pX:
            print('NO')
            break
    if not pX:
        print(''.join(sorted(m)))


n=int(input())
m=[]
sc=[]
for i in range(n):
    m.append(input())
    sc.append(set(m[i]))
    if len(sc[i])!=len(m[i]):
        print('NO')
        break
else:
    i=0
    pX=False
    while i<len(m):
        j=i+1
        p=False
        while j<len(m):
            #print(m)
            z=len(sc[i].intersection(sc[j]))
            #a=len(sc[i])
            #b=len(sc[j])
            if m[i] in m[j]:
                m[i]=m[j]
                sc[i]=sc[j]
                sc.pop(j)
                m.pop(j)
                p=True
                break
            elif m[j] in m[i]:
                sc.pop(j)
                m.pop(j)
                j-=1
            elif z>0:
                if m[i][-z:]==m[j][:z]:
                    m[i]+=m[j][z:]
                elif m[j][-z:]==m[i][:z]:
                    m[i]=m[j]+m[i][z:]
                else:
                    pX=True
                    break
                sc[i]=set(m[i])
                m.pop(j)
                sc.pop(j)
                j-=1
                p=True
            j+=1
        if not p:
            i+=1
        if pX:
            print('NO')
            break
    if not pX:
        print(''.join(sorted(m)))

u, v, d = {}, {}, set()
for i in range(int(input())):
    t = input()
    if len(t) == 1: d.add(t)
    for a, b in zip(t, t[1:]):
        if u.get(a, b) != b or v.get(b, a) != a: print('NO');return
        u[a], v[b] = b, a
d = d - set(u) - set(v)
for q in set(u).difference(v):
    while q[-1] in u: q += u.pop(q[-1])
    d.add(q)
if u: print('NO');return
print(''.join(sorted(d)))

u, v, d = {}, {}, set()
for i in range(int(input())):
    t = input()
    if len(t) == 1: d.add(t)
    for a, b in zip(t, t[1:]):
        if u.get(a, b) != b or v.get(b, a) != a: print('NO');return
        u[a], v[b] = b, a
x, y = set(u), set(v)
d = d - x - y
for q in x - y:
    while q[-1] in u: q += u.pop(q[-1])
    d.add(q)
if u: print('NO');return
print(''.join(sorted(d)))

n = int(input())
u = []
s = []
ok = True
for i in range(n):
    u.append(input())
    s.append(set(u[i]))
    if len(s[i]) != len(u[i]):
        print('NO')
        ok = False
        break
if ok:
    i = 0
    ok = False
    while i < len(u):
        j = i + 1
        p = False
        while j < len(u):
            z = len(s[i].intersection(s[j]))
            if u[i] in u[j]:
                u[i] = u[j]
                s[i] = s[j]
                s.pop(j)
                u.pop(j)
                p = True
                break
            elif u[j] in u[i]:
                s.pop(j)
                u.pop(j)
                j -= 1
            elif z > 0:
                if u[i][-z:] == u[j][:z]:
                    u[i] += u[j][z:]
                elif u[j][-z:] == u[i][:z]:
                    u[i] = u[j] + u[i][z:]
                else:
                    ok = True
                    break
                s[i] = set(u[i])
                u.pop(j)
                s.pop(j)
                j -= 1
                p = True
            j += 1
        if not p:
            i += 1
        if ok:
            print('NO')
            break
    if not ok:
        u.sort()
        print(''.join(u))
        






                


#https://codeforces.com/problemset/problem/886/D
def is_all_used(used):
    for val in list(used.values()):
        if val != True:
            return False
    return True    

def is_circle(d, pre):
    used     = {x:False for x in d}
    pre_none = [x for x in used if x not in pre]
    s_arr    = []
    
    for x in pre_none:
        cur    = []
        flg    = dfs(x, d, used, cur)
            
        if flg==True:
            return True, None
            
        s_arr.append(cur)
    
    if is_all_used(used) != True:
        return True, None
    
    return False, s_arr

def dfs(u, d, used, cur):
    used[u] = True
    cur.append(u)
    flg = False
    
    for v in d[u]:
        if used[v] == True:
            return True
        
        flg = dfs(v, d, used, cur)
        
        if flg==True:
            return flg
    return flg

def push(d, u, v=None):
    if u not in d:
        d[u] = set()
    
    if v is not None:
        if v not in d:
            d[v] = set()
        d[u].add(v)
    
def push_p(d, v):
    if v not in d:
        d[v] = 0
    d[v]+=1
    
def is_deg_valid(d):
    for u in d:
        if len(d[u]) > 1:
            return True
    return False

def solve():
    n   = int(input())
    d   = {}
    pre = {}
    
    for _ in range(n):
        s = input()
        if len(s) == 1:
            push(d, s)
        else:
            for u, v in zip(s[:-1], s[1:]):
                push(d, u, v)
                push_p(pre, v)
    
    flg, arr = is_circle(d, pre)
    
    if is_deg_valid(d) or flg==True:
        return 'NO'
    
    S = [''.join(x) for x in arr]
    S = sorted(S)
    return ''.join([s for s in S])
        
print(solve())

#4
#mail
#ai
#lru
#cf

#3
#kek
#preceq
#cheburek


L = {}
R = {}
S = set()

for _ in range(int(input())):
    s = input()
    if len(s) == 1: 
        S.add(s)
    for s1, s2 in zip(s, s[1:]):
        if  s2 != L.get(s1, s2) or s1 != R.get(s2, s1): 
            print('NO');return
        L[s1], R[s2] = s2, s1

L1, R1 = set(L), set(R)
S = S -L1 - R1

for i in L1 - R1:
    while i[-1] in L: 
        i += L.pop(i[-1])
    S.add(i)
if L: 
    print('NO');return
print(''.join(sorted(S)))

StringsNumber = int(input())
FinalStrings = []
Strings = []

for i in range(StringsNumber):
    Strings.append(input())

LetterGraph = {}

# Генерим граф

for i in range(len(Strings)):
    if len(Strings[i]) == 1:
        if Strings[i] not in LetterGraph:
            LetterGraph[Strings[i]] = ""
            #print("заапедил", i)
        continue
    for e in range(len(Strings[i]) - 1):
        if Strings[i][e] not in LetterGraph:
            Elements = []
            for j in list(LetterGraph):
                if j != Strings[i][e + 1]:
                    Elements.append(LetterGraph[j])

            if Strings[i][e + 1] in Elements:
                print("NO")
                return
            LetterGraph[Strings[i][e]] = Strings[i][e + 1]
            continue
        if LetterGraph[Strings[i][e]] == Strings[i][e + 1] or LetterGraph[Strings[i][e]] == "":
            LetterGraph[Strings[i][e]] = Strings[i][e + 1]
            continue
        #print("Граф:", LetterGraph)
        print("NO")
        return

#print("Я сгенерил граф, получилось:", LetterGraph)

# Проверяем, что нету цикла

if LetterGraph:
    Cycle = False
    for i in LetterGraph:
        Letter = LetterGraph[i]
        while True:
            if Letter in LetterGraph:
                if LetterGraph[Letter] == i:
                    print("NO")
                    return
                Letter = LetterGraph[Letter]

            else:
                break

# Находим возможные первые символы

if LetterGraph:
    IsIFirstSymbol = False
    FirstSymbols = []

    for i in LetterGraph:
        IsIFirstSymbol = True
        for e in LetterGraph:
            if LetterGraph[e] == i:
                #print(i, "не подходит, потому что", e, "указывает на него.")
                IsIFirstSymbol = False
        if IsIFirstSymbol:
            FirstSymbols.append(i)

    if not FirstSymbols:
        print("NO")
        return

#print("Варианты первого символа:", *FirstSymbols)

# Создаем варианты финальной строки

if LetterGraph:
    Letter = ""
    for i in FirstSymbols:
        FinalString = i
        Letter = i
        for e in range(len(LetterGraph)):
            if Letter in LetterGraph:
                if not (LetterGraph[Letter] == ""):
                    FinalString += LetterGraph[Letter]
                    #print(Letter, "есть в графе, так что добавляем", LetterGraph[Letter], ", на которое оно указывает.")
                    Letter = LetterGraph[Letter]
                else:
                    break
            else:
                break

        FinalStrings.append(FinalString)

#print("Отдельные строки", *FinalStrings)

FinalStrings.sort()

RESULT = ""

for i in FinalStrings:
    RESULT += i

print(RESULT)


def generate_good_string(subs : list):
    In, Out, S = {}, {}, set()
    for s in subs:
        if len(s) == 1:
            S.add(s) 
        for fr, to in zip(s, s[1:]):
            if fr != In.get(to, fr) or to != Out.get(fr, to):
                return(print('NO'))
            Out[fr], In[to] = to, fr
    Outset, Inset = set(Out), set(In)
    S -= (set.union(Outset, Inset))
    for s in Outset - Inset:
        while Out.get(s[-1]):
            s += Out.pop(s[-1])
        S.add(s)
    print('NO' if Out else ''.join(sorted(S)))
substrings = [input() for _ in range(int(input()))]
generate_good_string(substrings)