Vova created a topic classifier for problems on Timus Online Judge.
All topics form a tree, that is, every topic can have several possible subtopics.
For example, topic “geometry” in Vova’s classifier has two subtopics “technique geometry” and
“idea geometry”.
For every topic you are given an example of problems, that belong to it.
One problem can belong to several topics. For example, problem 1065 belongs to topics
“graphs” and “technique geometry”.
Using a given classifier, for each mentioned problem determine to which topics
it belongs.
Input
Input format is the same as in sample test.
Here are some input data limitations:
- Input data contains no more than 20 different topics and no more
than 20 different problem numbers.
Some topics can contain all of the given problems, some can contain
no problems at all.
- All problem numbers vary from 1000 to 9999.
List of problems for a topic can contain several lines, but each
line will contain at least one problem number.
No problem number will occur twice in the list for one topic.
- Topic names are non-empty srtings not longer than 20 symbols.
They consist of lower-case latin letters and spaces.
The first and the last symbols in a topic name are not spaces. There will be no
consecutive spaces in a topic name.
- Topic id is a sequence
<number>.<number>. ... <number>.
All numbers are integers from a segment [1, 20] and have no leading zeroes.
All topic id’s are unique.
- First topic’s id is “1.”
- If topic A listed before topic B, then either id of B contains id of
A as a prefix, or the leftmost number in which two id’s differ, is greater in id of B.
- If a topic id is “X.” or ends with “.X.”,
where
X is greater than 1, then earlier in the classifier there was a topic
with similar id, but with suffix “X.” replaced with “Y.”, where Y = X − 1.
- If a topic id ends with “.1.”, then topic listed directly befor it has
the same id without the last “1.”
Output
For every problem list all topics it belongs to, as it shown in the example.
Topic description should contain its name and names of all ancestor topics.
If a problem belongs to several topics, you should output topic descriptions divided
by commas and spaces (as shown in the sample test). If some problems have absolutely identical set of topics, descriptions for these problems should be united (just list all such problems separated by comma and space, and then print the topics).
Problem numbers should be listed in ascending order, topic descriptions — in lexicographic order.
All lines in the output shoud also be ordered lexicographically.
Sample
| input | output |
|---|
1. graphs
1022
1065
2. geometry
1020
2.1. idea
1130
2.2. technique
1111 1065
1265
2.2.1. convex hull
1271
3. dynamic programming
1244
| 1020 : geometry
1022 : graphs
1065 : geometry.technique, graphs
1111, 1265 : geometry.technique
1130 : geometry.idea
1244 : dynamic programming
1271 : geometry.technique.convex hull
|
Problem Author: Mikhail Rubinchik
