ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Astronomical Database

Time limit: 2.0 second
Memory limit: 64 MB
After the Hubble telescope had been orbited the number of known stars increased. Imagine how it will grow in the future when the mankind masters the hyperspace jump!
The farsighted astronomers want to get ready for that moment right now. They create a control system for a database of all known stars. The database will be multiuser and astronomers all over the world will be able to fill it with useful data. To improve the software's usability it's necessary to implement the popup prompting: when a new character is typed, the software must suggest the list of stars whose names start with the already typed characters. You are to help astronomers with their cosmic problem and to develop a prototype of the algorithm that will be used in the database control system in the future.


Each input line consists of one operation. The first character denotes the type of the operation. The rest of the characters (small Latin letters or digits) are the operation's argument.
The operation types are as follows:
'+' — add a star's name to the database. The argument of this operation is the name of the star that is to be added to the database. As the database is multiuser, the information concerning one star may be added several times. When the program is launched, the database contains a single word "sun".
'?' — find all the names that start with the characters given in the operation's argument.
There are not more than 10000 operations in the input and all the arguments contain not less than one and not more than 20 characters.


For a given '+' operation you should output nothing.
For each '?' operation output a respond to the query: the argument of the operation and then a list of stars' names that start with the given characters and that are presented in the database at the moment of the query.
The stars' names must be given in the lexicographical order, one in each line without repetitions.
If the length of the resulting list exceeds 20, then you should output the first 20 names only. Each name must be preceded by two spaces as it is shown in the sample (the spaces are replaced with dots in order to make the sample more illustrative).


Problem Author: Pavel Egorov
Problem Source: The Ural State university Championship, October 29, 2005
To submit the solution for this problem go to the Problem set: 1414. Astronomical Database