GCPC11E - Magical Crafting

no tags 

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

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 m1, m2, and m3 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

hide comments
Adrian Kuegel: 2011-11-07 09:03:26

l^3 * R sounds good, this is the intended complexity.

Mohammad F. Aziz: 2011-11-05 13:10:02

My best shot is O(l^3*R) and I still can't get any better approach. What's the complexity that the problem setter suggests? Sorry for my bad english....


Added by:Adrian Kuegel
Date:2011-07-05
Time limit:3.251s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Moritz Kobitzsch)