Magical Crafting

One of the recent hits among indie games has been Minecraft, a cute little game in which you mine materials and craft all sorts of things from them. Having already mastered the Minecraft universe, you decide to write your own little mod that adds magical crafting.

For a magic craft you start with a single block of magic stone m1 = 'A'. A crafting recipe lets you spend a fixed number of diamonds to transform one magic stone m1 into two magic stones m2 ∈ 'A'...'Z' and m3 ∈ 'A'...'Z'; these binary recipes are exactly the ones listed in the input. Separately, any magic stone m can be turned into its matching final glow stone — for example the magic stone 'A' becomes the glow stone 'a', its lowercase letter. This glow transformation is available for every magic stone, always costs exactly 1 diamond, and is not one of the listed recipes; a glow stone is final and cannot be transformed further. In this way you want to be able to craft wonderful magic lights for your own world.

But because you know how rare precious diamonds are, and because you are very picky about the lighting effects you want, you have to test your recipes. The question is whether your set of crafting recipes lets you create all of your desired lighting effects, and how many diamonds you would need.

The first line of input gives the number of test cases C (0 < C ≤ 100).

Each test case starts with two integers 0 ≤ R ≤ 30 and 0 ≤ L ≤ 10 on one line, the number of recipes and the number of lighting effects. The next R lines contain the recipes. Each recipe is given on one line by the magic stones m1, m2 and m3 together with the number of diamonds needed 0 ≤ d ≤ 1 000. The next L lines contain the lighting effects you want to achieve. Each such line contains an integer 1 ≤ l ≤ 100, the length of the lighting effect, followed by a single string of length l consisting only of lowercase letters a...z, the glow stones that make up the effect.

For each test case, print "CASE #" followed by the number of the test case (starting from 1) on its own line. Then, for each lighting effect, print one line: if the effect can be crafted, print "POSSIBLE WITH X DIAMONDS", where X is the minimum number of diamonds needed to achieve it; otherwise print "IMPOSSIBLE".