case class TrieNode(var count: Int = 0,
  val children: Map[Char, TrieNode] = Map.empty) {}

class Trie {
    private val root = new TrieNode()

  def add(word: String) = 
    word.foldLeft(root) { case (depth,char) => {
      depth.children
        .getOrElseUpdate(char, new TrieNode())
        .tap(_.count += 1)}}

  def find(prefix: String): Int = 
    prefix.foldLeft(Option(root)) { (traverse, char) =>
      traverse.flatMap(_.children.get(char))} match {
        case Some(node) => node.count
        case None => 0 }
        
 }

def contacts ( queries: Array[Array[String]]): Array[Int] = {
  queries.foldLeft((new Trie(), ListBuffer.empty[Int])) {
    case ((trie,res),q) => q match {
      case Array("add",w) => trie.add(w)
        (trie,res)
      case Array("find",w) => 
        (trie,res.append(trie.find(w)))
  }}._2.toArray
}