The British Informatics Olympiad is the computing competition for schools and colleges. We are proud to present BIO'99.

The 1999 British Informatics Olympiad Final
Spy vs Spy - Part Two

You have just heard from your two spies that the budget problems extended to their sophisticated equipment; apparently both pieces of chalk broke. The upshot of the equipment failure is that the spies were unable to know for certain when they entered a room they had been in before. In other words some rooms might occur on a map more than once with different labels. The spies are conscientious, so each version of a room will have the correct number of corridors leading from it.

Write a program that reads in the details of the two maps and determines if they might represent the same complex. The first line will be a pair of integers, 1<=n<=100 then 1<=m<=100, specifying the rooms on each map. The next n lines will contain the first spy's map, and the following m lines the second spy's map. The format for these lines is the same as the previous part.

If the two maps might represent the same complex you should output n lines. The jth line should be a list of all room labels on the second spy's map that correspond to label j on the first spy's map. If there are multiple solutions you only need to print one. If the two maps cannot represent the same complex you should just output Different.

Sample Input

4 6
a 2 x 4
b 3
c 1
a 2 x 1
a 2 x 1
b 3
c 4
a 5 x 4
b 6
c 1

Sample Output

1 4
2 5
3 6
1 4

The simplest map representing this complex would be defined by:

a 2 x 1
b 3
c 1

In other words, either of the two maps in the sample input can be compared wih this map and shown to be equivalent.

• Index of BIO'99 final