Phone Directory Search

You are building a phone directory application where users can enter names and their corresponding phone numbers. Implement a trie that allows for efficient insertion and search based on prefixes of names. The input consists of a sequence of commands: 1. 'ADD <name> <phone>' - Add a person's name and phone number to the directory. 2. 'SEARCH <prefix>' - Output all names whose names begin with the given prefix. Each result should be printed on a new line and sorted alphabetically. Example: INPUT: ADD Alice 1234 ADD Alex 5678 SEARCH Al SEARCH A OUTPUT: Alex Alice