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 // deal with shorter strings with same prefix as previous 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) { mutableListOf() } prefixes.zipWithNext().forEach { (a, b) -> // check the first char when { a.first() != b.first() -> isAfterNode[b.first() - 'a'].add(a.first()) else -> when { a.length == 1 -> Unit b.length == 1 -> return println("impossible") a == b -> Unit a.length == b.length -> isAfterNode[b.last() - 'a'].add(a.last()) else -> System.err.println("Skipping case a=$a and b=$b") } } } // 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) { // if we get here, if have a dependency loop return println("impossible") } loopSize[current.index] = queue.size queue.addLast(current) } // check the new alphabet tells us it is sorted (unnecessary?) val lookup = answer.withIndex().associateBy({ it.value }) { it.index } if (prefixes.zipWithNext().all { (a, b) -> when { a.first() != b.first() -> lookup[a.first()]!! <= lookup[b.first()]!! a.length != b.length -> true else -> lookup[a.last()]!! <= lookup[b.last()]!! } }) { println(answer.joinToString(separator = "")) } else { println("impossible") } }