Contact Search with Prefix

You are tasked with implementing a contact search system. Your task is to create a Trie data structure that can handle adding contact names and searching for contacts by prefix. Implement the following methods: 1. `add_contact(name: str)` - adds a contact name to the trie. 2. `search_prefix(prefix: str) -> List[str]` - returns a list of all contact names that start with the given prefix in lexicographical order. Input format: - The first line contains an integer, N (1 ≤ N ≤ 1000), the number of operations. - The following N lines contain operations in the format: - `add <name>` (where <name> is a string containing alphabetic characters), - `search <prefix>` (where <prefix> is a string). Output format: - For each `search` operation, print the list of found names in a single line, separated by spaces, or '[]' if no names matched. Example: Input: 5 add Alice add Alex add Bob search Al search B Output: Alice Alex Bob