Design Search Autocomplete System

You are given a list of historical sentences `sentences` and an integer array `times`, where `sentences[i]` is a previously typed sentence and `times[i]` is the number of times it has been typed. Implement the `AutocompleteSystem` class: - `AutocompleteSystem(String[] sentences, int[] times)` initializes the system with the given sentences and their corresponding frequencies. - The method `List input(char c)` is called whenever the user types a character `c`: - If `c` is not the character `'#'`, append `c` to the current input prefix and return the top 3 historical sentences that have the current prefix. The returned sentences should be sorted by: 1. Highest frequency of occurrence. 2. If frequencies are equal, lexicographically smaller sentence first. - If `c` is the character `'#'`, the current input prefix is considered a completed sentence. Add it to the historical records (or increment its frequency if it already exists), reset the current prefix to empty, and return an empty list. You should design the system to efficiently support up to 5000 calls to `input`. **Constraints:** - `n == sentences.length == times.length` - `1 <= n <= 100` - `1 <= sentences[i].length <= 100` - `1 <= times[i] <= 50` - Each sentence consists of lowercase letters and spaces. - The input character `c` is a lowercase letter, a space `' '`, or `'#'`. - The total number of characters input via `input` will not exceed 200. Return the list of top 3 matching sentences for each call to `input` (except when `c == '#'`, in which case return an empty list).