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

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue