Magical Crafting
One of the recent hypes in terms of independent games has been Minecraft, a cute little game in which you mine some materials and are able to craft a lot of stuff using these materials. Since you already mastered the Minecraft universe, you decide to write your own little mod for the game to add magical crafting.
Given some magic stone m_1, by adding a specific amount of diamonds you can transform it into two magic stones m_{2 }and m_3, where m_1, m_2 and m_3 are upper-case letters. This is called a crafting recipe.
There is also a default transformation which transforms a magic stone into its matching lighting effect; the matching lighting effect for a magic stone labelled with an upper-case letter is the corresponding lower-case letter, e. g. the magic stone 'A' can be transformed into the lighting effect 'a'. This transformation always costs exactly 1 diamond. The default transformation is used whenever you do not use a magic stone for another crafting recipe. The lighting effects will show in a certain order. For each used crafting recipe m_1 -> m_2m_3, the lighting effects which are derived from the magic stone m_2 will show before the lighting effects derived from the magic stone m_3.
You want to be able to craft wonderful magic lights for your own world. But as you are aware of the rareness of the precious diamonds, and also very picky about the lighting effect sequences you want to achieve, you have to test your crafting recipes. The question arises if your set of crafting recipes allows you to create all your desired lighting effect sequences if you only have the magic stone 'A' to start with, and the minimum number of diamonds you will need for the transformations.
Input
The first line of the input gives the number of test cases C (0 < C ≤ 100). Each test case starts with two integers 0 ≤ R ≤ 30, 0 ≤ L ≤ 10 on a single line, denoting the set of recipes and the number of lighting effect sequences. The next Rlines contain the set of recipes. Each crafting recipe is given on a single line by the magic stones m_1, m_2, and m_3 as well as the number d (0 ≤ d ≤ 1000) of diamonds necessary for the transformation. The next L lines contain the lighting effect sequences you want to create. Each of these lines contains an integer l (1 ≤ l ≤ 100), which represents the length of the lighting effect sequence. The line completes with a single string of length l, consisting only of lower case characters 'a' to 'z', which represents the sequence of lighting effects you want to create.
Output
For every test case print CASE # followed by the number of the test case, starting with 1, on a single line. For each lighting effect sequence print a single line. If the effect is possible print POSSIBLE WITH X DIAMONDS, with X representing the number of diamonds you will need to achieve the lighting effect sequence. In the case the lighting effect sequence cannot be crafted, print IMPOSSIBLE.