Implement a search autocomplete suggestion service

Design an autocomplete component that suggests the most relevant search phrases as a user types. You are given historical sentences with their usage counts. The system receives the query one character at a time and must return suggestions after each character. ### Requirements - Initialize with: - `sentences[i]`: a previously typed sentence - `times[i]`: how many times it was typed - On each input character `c`: - If `c != '#'`, append it to the current query prefix and return the **top 3** matching historical sentences that start with this prefix. - If `c == '#'`, treat the current query as a completed sentence: - increment its count by 1 (add it if new) - clear the current query - return an empty list ### Ranking - Higher count ranks first. - Ties are broken by lexicographically smaller sentence first. ### API Implement a class with methods: - `AutocompleteSystem(sentences, times)` - `input(c) -> List[str]` ### Constraints (reasonable interview constraints) - Number of historical sentences: up to `2 * 10^4` - Sentence length: up to `100` - Number of `input()` calls: up to `2 * 10^4`