import java.util.* import kotlin.math.max fun main() { val n = readln().toInt() val words = System.`in`.bufferedReader().lineSequence().take(n).toList() var lastPrefix = 0 // calculate all prefixes of the words var valid = true val prefixes = words.windowed(2, partialWindows = true) { list -> if (!valid) return@windowed "" val current = list[0] val next = if (list.size == 2) list[1] else "" // prefix of last and current val nextPrefix = current.indices.firstOrNull { it >= next.length || next[it] != current[it] }?.let { if (it + 1 <= current.length && it + 1 <= next.length) it + 1 else it } ?: current.length if (nextPrefix > 0 && nextPrefix == next.length && nextPrefix < current.length && current.substring( 0, nextPrefix ) == next ) { valid = false return@windowed current } val prefix = max(lastPrefix, nextPrefix) lastPrefix = nextPrefix current.substring(0, prefix) } if (!valid) return println("impossible") // Based on the prefixes learn if a letter is after another letter val isAfterNode = Array>(26) { mutableSetOf() } fun findLastCommonIndex(a: String, b: String): Int { var index = 0 while (a[index] == b[index] && index+1 < a.length && index+1 < b.length) index++ return index } prefixes.zipWithNext().forEach { (a, b) -> // check the first char if (a == b) return@forEach val index = findLastCommonIndex(a, b) if (index == b.length) return println("impossible") else if (b[index] != a[index]) isAfterNode[b[index ] - 'a'].add(a[index ]) } // build the alfabet val queue = isAfterNode.withIndex().sortedBy { it.value.size }.toCollection(LinkedList()) val seen = BooleanArray(26) val answer = mutableListOf() val loopSize = IntArray(26) // loop detection while (queue.isNotEmpty()) { val current = queue.removeFirst() if (current.value.all { seen[it - 'a'] }) { seen[current.index] = true answer.add('a' + current.index) continue } if (loopSize[current.index] == queue.size) { return println("impossible") } loopSize[current.index] = queue.size queue.addLast(current) } println(answer.joinToString(separator = "")) }