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

2074. Timus problems classifier

Time limit: 2.0 second
Memory limit: 256 MB
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:
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. First topic’s id is “1.”
  6. 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.
  7. 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.
  8. 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

inputoutput
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