Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1774
Somebody Save the Prince

Time Limit: 2 Seconds      Memory Limit: 65536 KB

On his way to save his damsel in distress, Prince Charming was delayed by the beguiling ways of Mab, the evil enchantress. Mab had managed to trap him in an underground dungeon, where the only way out was through a steel door. (It seems Prince Charming won't be doing any saving any time soon.)

However, Mab was given orders (by the author of the fairytale, who else?) to give someone a chance to free Prince Charming. Upon hearing this, she cast a spell on the door such that when an outsider (like you) wrote the magic password on it, it would unlock to free the prince. To give you a chance to figure out the word, she left a cube full of letters and a list of words outside the door.

The cube contains a jumble of letters arranged in such a way that there are as many layers as there are letters along the length and breadth of each layer of the cube. The words in the list contain the words you will need to find in the cube in order to figure out the magic password.

The words can be found arranged in a line in the cube. For the example above, they can be arranged like C-F-I, G-M-S, or I-N-S.

Once you have found a word, find the letter before the first letter of the word and keep it for later. For the example above, if the word is "MY", the letter to keep is "A". However, if the first letter is at the edge of the cube, you will need to find the letter after the last letter of the word. For example, if the word is "IN", the letter to keep is "S".

Ordering the letters found according to the original list of words will form the magic password.

Take note that not all words in the list are in the cube.


The input contains only one test case. The first line consists of integers n and m where n represents the number of words in the list, and m represents the number of layers in the cube. The next n lines are the words in the list. The m lines that follow these consist of one layer, with each row of a layer separated by a comma, read back to front. The maximum number of layers is 20. The maximum number of words is 100.


A group of letters ordered according to the list of words they are associated with. Leading or trailing white space characters are not allowed.

Sample Input


Sample Output


Source: Asia 2003, Manila (Philippine)
Submit    Status