마법 제작

최근 인디 게임 중 크게 인기를 끈 것 중 하나가 마인크래프트입니다. 재료를 캐서 그 재료로 온갖 것을 제작할 수 있는 아기자기한 게임이죠. 이미 마인크래프트의 세계를 통달한 당신은, 마법 제작(magical crafting)을 추가하는 나만의 작은 모드를 직접 만들기로 합니다.

마법 제작에서는 마법석 한 덩이 m1 = 'A'에서 시작합니다. 제작법(recipe)은 정해진 수의 다이아몬드를 들여 마법석 하나 m1을 두 개의 마법석 m2 ∈ 'A'...'Z'와 m3 ∈ 'A'...'Z'로 바꾸는 것이며, 이러한 이항(두 개로 나누는) 제작법이 바로 입력에 주어지는 것들입니다. 이와 별개로, 어떤 마법석 m이든 그에 대응하는 최종 발광석으로 바꿀 수 있습니다. 예를 들어 마법석 'A'는 발광석 'a'(그 소문자)가 됩니다. 이 발광석 변환은 모든 마법석에 대해 언제나 사용할 수 있고, 항상 정확히 다이아몬드 1개가 들며, 입력에 주어지는 제작법에는 포함되지 않습니다. 발광석은 최종 형태여서 더 이상 변환할 수 없습니다. 이렇게 해서 당신은 자신만의 세계를 위한 멋진 마법 조명을 만들고자 합니다.

하지만 귀한 다이아몬드가 얼마나 드문지 잘 알고 있고, 원하는 조명 효과에 대해서도 매우 까다롭기 때문에, 제작법을 시험해 봐야 합니다. 문제는, 당신이 가진 제작법들로 원하는 모든 조명 효과를 만들 수 있는지, 그리고 그러려면 다이아몬드가 몇 개 필요한지입니다.

입력의 첫째 줄에는 테스트 케이스의 수 C (0 < C ≤ 100)가 주어집니다.

각 테스트 케이스는 한 줄에 두 정수 0 ≤ R ≤ 30과 0 ≤ L ≤ 10으로 시작하며, 이는 제작법의 수와 조명 효과의 수입니다. 이어지는 R개의 줄에는 제작법이 주어집니다. 각 제작법은 한 줄에 마법석 m1, m2, m3과 함께 필요한 다이아몬드의 수 0 ≤ d ≤ 1 000으로 주어집니다. 그다음 L개의 줄에는 당신이 만들고자 하는 조명 효과가 주어집니다. 각 줄에는 조명 효과의 길이를 나타내는 정수 1 ≤ l ≤ 100이 있고, 이어서 길이가 l이며 소문자 a...z로만 이루어진 문자열 하나가 오는데, 이는 그 효과를 이루는 발광석들입니다.

각 테스트 케이스마다 한 줄에 "CASE #" 뒤에 테스트 케이스 번호(1부터 시작)를 붙여 출력합니다. 그다음, 각 조명 효과마다 한 줄을 출력합니다. 그 효과를 만들 수 있으면 "POSSIBLE WITH X DIAMONDS"를 출력하며, 여기서 X는 그 효과를 이루는 데 필요한 최소 다이아몬드의 수입니다. 만들 수 없으면 "IMPOSSIBLE"을 출력합니다.