Something that is very easy to do is "a piece of cake". This problem is not very easy, but this is easy enough as this is about some pieces of cake.
There are many different styles of cake as you may already know e.g. chocolate cake, cream cake, tiramisu, cheesecake, etc… Each piece of cake may be of different integral size. Your task is simply sort the list of available pieces of cake according to your friends’ preference. Say the available pieces of cake are: Chocolate of size 3, Tiramisu of size 2, Black Forest of size 2, Strawberry Cheesecake of size 1, Tiramisu of size 1 and Black Forest of size 1. Your friend prefers Tiramisu over Black Forest over Chocolate and she prefers smaller piece of cake. Given her preference, you would give her the sorted list of cake: Tiramisu of size 1, Tiramisu of size 2, Black Forest of size 1, Black Forest of size 2, Chocolate of size 3. Note that Strawberry Cheesecake is not listed as she did not mention she wants this style of cake.
Input will start with an integer c which is the number of test cases. Each test case will start with an integer n (n<100), n lines follow giving you the list of available pieces of cake. Each of these n lines will start with the name of the cake style (less than 100 characters, there are no spaces to the left and right of the names), and then an integer s which is the size of the piece of cake (2^0 <= s <= 2^32) follows with a space between the name and the size. After n lines, there will be an integer p which is the length of the preference list. Each of the follow p lines will contain the cake style in order. Each test case will end with an integer which can be either 0 (prefer smaller cake) or 1 (prefer larger cake).
The first sample input corresponds to the example in problem description.
Print the sorted list of cake as described in the problem description. Refer to sample output for the format. Print a blank line between consecutive cases.
If no available cakes for your friend just print one line “Do you know what does a piece of cake mean?”
Do not worry about input size and efficiency of your sorting algorithm. The input size is very small so that even the famous LD-sort will be efficient enough for this problem.
2 6 Chocolate 3 Tiramisu 2 Black Forest 2 Strawberry Cheesecake 1 Tiramisu 1 Black Forest 1 3 Tiramisu Black Forest Chocolate 0 6 Chocolate 3 Tiramisu 2 Black Forest 2 Strawberry Cheesecake 1 Tiramisu 1 Black Forest 1 3 Tiramisu Black Forest Bitter Chocolate with Hazelnut Mousse 1
Tiramisu 1 Tiramisu 2 Black Forest 1 Black Forest 2 Chocolate 3 Tiramisu 2 Tiramisu 1 Black Forest 2 Black Forest 1