text: # Time:  O(p^2), p is the length of the prefix
  # Space: O(p * t + s), t is the number of nodes of trie
  #                    , s is the size of the sentences
  
  import collections
  
  class TrieNode(object):
  
      def __init__(self):
          self.__TOP_COUNT = 3
          self.infos = []
          self.leaves = {}
  
      def insert(self, s, times):
          cur = self
          cur.add_info(s, times)
          for c in s:
              if c not in cur.leaves:
                  cur.leaves[c] = TrieNode()
              cur = cur.leaves[c]
              cur.add_info(s, times)
  
      def add_info(self, s, times):
          for p in self.infos:
              if p[1] == s:
                  p[0] = -times
                  break
          else:
              self.infos.append([-times, s])
          self.infos.sort()
          if len(self.infos) > self.__TOP_COUNT:
              self.infos.pop()
  
  class AutocompleteSystem(object):
  
      def __init__(self, sentences, times):
          """
          :type sentences: List[str]
          :type times: List[int]
          """
          self.__trie = TrieNode()
          self.__cur_node = self.__trie
          self.__search = []
          self.__sentence_to_count = collections.defaultdict(int)
          for sentence, count in zip(sentences, times):
              self.__sentence_to_count[sentence] = count
              self.__trie.insert(sentence, count)
  
      def input(self, c):
          """
          :type c: str
          :rtype: List[str]
          """
          result = []
          if c == '#':
              self.__sentence_to_count["".join(self.__search)] += 1
              self.__trie.insert("".join(self.__search), self.__sentence_to_count["".join(self.__search)])
              self.__cur_node = self.__trie
              self.__search = []
          else:
              self.__search.append(c)
              if self.__cur_node:
                  if c not in self.__cur_node.leaves:
                      self.__cur_node = None
                      return []
                  self.__cur_node = self.__cur_node.leaves[c]
                  result = [p[1] for p in self.__cur_node.infos]
          return result
  
  