Prefix Based Database

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.

Input

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.

Output

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.

Examples

Input
Output
9 add cat add code add core search co add profound add found search fo add fight search f
code core found fight found
Β 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 15 MB

To check your solution you need to sign in
Sign in to continue