Contact Manager

You are required to implement a Contact Manager that supports a series of operations to manage contact data. Each contact consists of a unique name and an associated phone number. The Contact Manager must support the following operations:

1. ADD name phone: Add a new contact with the given name and phone number. If the contact already exists, the phone number should be updated.
2. DELETE name: Delete the contact with the specified name. If the contact exists, output: (\text{Contact 'name' deleted.}) Otherwise, output: (\text{Contact not found}).
3. GET name: Retrieve the phone number for the specified name. If the contact is not found, output: (\text{Contact not found}).
4. LIST: List all contacts sorted in lexicographical order by name. Each contact should be displayed in the format "Name: Phone" on a separate line.

Input is received from standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains an integer (Q) representing the number of operations to process. Each of the next (Q) lines contains one of the following commands:

• ADD name phone – Add or update a contact
• DELETE name – Delete a contact
• GET name – Retrieve a contact's phone number
• LIST – List all contacts in lexicographical order

Note: "name" and "phone" are strings without spaces.

outputFormat

For each GET and DELETE command, output the corresponding result on a new line. For GET, output the phone number if the contact exists or "Contact not found" otherwise. For DELETE, output "Contact 'name' deleted." if the contact is removed successfully, or "Contact not found" if it does not exist. For the LIST command, output each contact on a new line in the format "Name: Phone". If there are no contacts, output nothing.## sample

4
ADD Alice 123-456-7890
GET Alice
ADD Alice 111-222-3333
GET Alice

123-456-7890
111-222-3333