data class TrieNode(val char: Char?, var searchResult: Int,  val children: MutableList<TrieNode>) {
    constructor(char: Char?, children: MutableList<TrieNode>): this(char, 1, children)
}

fun contacts(queries: Array<Array<String>>): Array<Int> {
    val res = mutableListOf<Int>()
    val root = TrieNode(null, mutableListOf())
    queries.forEach { query->
        val command = query[0]
        val name = query[1]
        if (command=="add") {
            var temp = root
            for (i in name.indices) {
                val nodeToFind = temp.children.firstOrNull({it.char == name[i]})
                if (nodeToFind==null) {
                    val newNode = TrieNode(name[i], mutableListOf())
                    temp.children.add(newNode)
                    temp = newNode
                } else {
                    nodeToFind.searchResult++
                    temp = nodeToFind
                }
            }
        } else {
            res.add(foundResult(name, root))
        }
    }
    
    return res.toTypedArray()
}

fun foundResult(keyword: String, root: TrieNode): Int {
    var temp = root
    for (i in keyword.indices) {
        val nodeToFind = temp.children.firstOrNull({it.char == keyword[i]})
        if (nodeToFind==null) {
            return 0
        } else {
            temp = nodeToFind
        }
    }
    return temp.searchResult
}