packed-prefix

import java.util.Stack

/**
 * https://contest.yandex.ru/contest/26133/run-report/112160601/
 *
 * ПРИНЦИП РАБОТЫ
 * Каждая запакованная строка распаковывается и добавляется в экземпляр класса [LongestCommonPrefix]. Сначала формируется
 * числовой коэффициент (число повторений запакованной части строки), далее извлекается запакованная часть.
 *
 * ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
 * В процессе распаковки контролируется длина распакованной части слова - если она превышает строку, которая хранится в [LongestCommonPrefix]
 * то дальнейшая распаковка не имеет смысла, т.к. НОП не может превышать длины самой короткой строки.
 *
 * ВРЕМЕННАЯ СЛОЖНОСТЬ
 * Сложность распаковки в среднем составит O (n * m), где n - количество строк, m - средняя длина строки
 * Сложность добавления слова в префикс составит O (n), где n - длина существующего префикса.
 *
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
 * Составит O (n), где n - длина наибольшей строки.
 */
fun packedPrefix(packedStrings: List<String>): String {
    val longestCommonPrefix = LongestCommonPrefix()
    for (packed in packedStrings) {
        packed.unpackTo(longestCommonPrefix)
    }
    return longestCommonPrefix.get()
}

private fun String.unpackTo(longestCommonPrefix: LongestCommonPrefix) {
    var multiplier = 1
    var i = 0
    var prefixIndex = 0
    val stack = Stack<Packed>()
    while (i < this.length) {
        val currentChar = this[i]
        when {
            currentChar.isDigit() -> {
                multiplier = currentChar.digitToInt()
            }
            currentChar == '[' -> {
                stack.push(Packed(multiplier, StringBuilder()))
            }
            currentChar == ']' -> {
                val unpackedPart = stack.pop().multipliedPart
                if (stack.isNotEmpty()) {
                    stack.peek().part.append(unpackedPart)
                } else {
                    // закончилась запакованная часть, посимвольно добавляем к результату
                    for (char in unpackedPart) {
                        if (!longestCommonPrefix.add(char, prefixIndex++)) {
                            return
                        }
                    }
                }
            }
            // is letter
            else -> {
                if (stack.isNotEmpty()) {
                    stack.peek().part.append(currentChar)
                } else {
                    // идём по строке без множителя
                    if (!longestCommonPrefix.add(currentChar, prefixIndex++)) {
                        return
                    }
                }
            }
        }
        i++
    }
    longestCommonPrefix.setCompleted()
}

private class LongestCommonPrefix {
    private val result = StringBuilder()
    private var completed = false

    fun add(char: Char, index: Int): Boolean {
        return when {
            // удлинение строящегося префикса
            ! completed && index == result.length -> {
                result.append(char)
                true
            }
            // проверка совпадения с существующим префиксом
            completed && index < result.length && char == result[index] -> {
                true
            }
            else -> {
                result.setLength(index)
                false
            }
        }
    }

    fun get(): String {
        return result.toString()
    }

    fun setCompleted() {
        completed = true
    }
}

private data class Packed(
    val multiplier: Int,
    val part: StringBuilder
) {
    val multipliedPart: String
        get() {
            val unpackedPart = StringBuilder()
            repeat(multiplier) {
                unpackedPart.append(part)
            }
            return unpackedPart.toString()
        }
}

fun main() {
    val reader = System.`in`.bufferedReader()
    val packedStringCount = reader.readLine().toInt()
    val packedStrings = List(packedStringCount) {
        reader.readLine()
    }

    println(packedPrefix(packedStrings))
}