import heapq
from collections import defaultdict
from typing import List


class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.historical_data = defaultdict(int)
        self.freq_sorted_sentences = []
        for sentence, count in zip(sentences, times):
            self.historical_data[sentence] = count
        self.curr_input = ''
        self.potential_sentences = sentences
        self.char_counter = 0
        self.ans = []

    def input(self, c: str) -> List[str]:
        if c == '#':
            self.historical_data[self.curr_input] += 1
            self.curr_input = ''
            self.char_counter = 0
            self.potential_sentences = []
            for sentence in self.historical_data.keys():
                self.potential_sentences.append(sentence)
            self.freq_sorted_sentences = []
            self.ans = []
            return []
        if c == '':
            return None
        self.curr_input += c
        self.ans = []
        further_potential_sentences = []
        for sentence in self.potential_sentences:
            if len(sentence)-1 < self.char_counter:
                continue
            if sentence[self.char_counter] == c:
                further_potential_sentences.append(sentence)
                heapq.heappush(self.freq_sorted_sentences,
                               (-1 * self.historical_data[sentence], sentence))
        self.potential_sentences = further_potential_sentences
        self.char_counter += 1
        try:
            self.ans.append(heapq.heappop(self.freq_sorted_sentences)[1])
            self.ans.append(heapq.heappop(self.freq_sorted_sentences)[1])
            self.ans.append(heapq.heappop(self.freq_sorted_sentences)[1])
        except IndexError:
            pass
        self.freq_sorted_sentences = []
        return self.ans