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₁, by adding a specific amount of diamonds you can transform it into two magic stones m₂ and m₃, where m₁, m₂ and m₃ 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₁ → m₂ m₃, the lighting effects which are derived from the magic stone m₂ will show before the lighting effects derived from the magic stone m₃.

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 R lines contain the set of recipes. Each crafting recipe is given on a single line by the magic stones m₁, m₂, and m₃ 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.

Example

Input:
2
1 4
A A A 2
3 aaa
8 aaaaaaaa
5 ababa
1 a
3 1
A B C 1
C P C 7
B I C 11
4 icpc

Output:
CASE #1
POSSIBLE WITH 7 DIAMONDS
POSSIBLE WITH 22 DIAMONDS
IMPOSSIBLE
POSSIBLE WITH 1 DIAMONDS
CASE #2
POSSIBLE WITH 23 DIAMONDS