You are given an empty database initially, and you need to handle a series of queries. There are two types of queries: "Add" and "Search." The "Add" query adds a name to the database, while the "Search" query asks you to output all the names in the database that start with a given prefix, in lexicographical order. However, if there are more than 20 names that match the given prefix, you should only output the first 20.
The input begins with an integer q (1 ≤ q ≤ 200 000) on the first line, representing the number of queries. The next q lines contain the queries in the following format:
For "Add" queries: add s (where s is the name to be added to the database).
For "Search" queries: search p (where p is the prefix to search for).
The length of the query strings does not exceed 20 characters.
For each "Search" query, output the names from the database that start with the given prefix, separated by a space. If there are more than 20 names that match the prefix, output only the first 20 names.