Birthday Reminder

Sophie wants to keep track of her friends' birthdays. Initially, she has a list of friends and their corresponding birthday months. She then performs a series of operations where she can add a new friend, update an existing friend's birthday month, or query which friends have birthdays in a given month. The operations need to be processed efficiently, as the number of initial entries can be up to \(10^5\) and the number of operations up to \(2 \times 10^5\). Use appropriate data structures to achieve the necessary efficiency.

inputFormat

The input is read from standard input as follows:

First line: an integer N, the number of initial friends (0 ≤ N ≤ 100000). Next N lines: each contains a string (friend's name) and an integer (birthday month, 1 to 12). The following line: an integer Q, the number of operations (up to 200000). Next Q lines: each line is an operation in one of the following formats:

• "ADD friend month" to add a new friend with the specified month.
• "UPDATE friend month" to update an existing friend's birthday month.
• "QUERY month" to query and list all friends with birthdays in that month in lexicographical order.

outputFormat

For each QUERY operation, output a single line. The line should contain the names of the friends who have their birthdays in the specified month, listed in lexicographical order and separated by a single space. If no friend has a birthday in that month, output "NONE".## sample

2
alice 1
bob 2
5
ADD charlie 3
UPDATE alice 2
QUERY 1
QUERY 2
QUERY 3

NONE
alice bob
charlie