Магическое ремесло
Одна из последних сенсаций в мире инди-игр — это Minecraft, очаровательная игра, в которой вы добываете материалы и создаете из них различные предметы. Освоив вселенную Minecraft, вы решили разработать собственный мод, добавляющий магическое крафтинг.
Имея магический камень m_1, вы можете, добавив определенное количество алмазов, превратить его в два магических камня m_2 и m_3, где m_1, m_2 и m_3 обозначены заглавными буквами. Это называется рецептом крафтинга.
Существует также стандартное преобразование, которое превращает магический камень в соответствующий световой эффект; для магического камня, обозначенного заглавной буквой, соответствующий световой эффект — это строчная буква, например, магический камень 'A' может быть преобразован в световой эффект 'a'. Это преобразование всегда стоит ровно 1 алмаз. Стандартное преобразование применяется, когда магический камень не используется в другом рецепте крафтинга. Световые эффекты отображаются в определенном порядке. Для каждого использованного рецепта крафтинга m_1 -> m_2m_3 световые эффекты, полученные из магического камня m_2, будут отображаться перед световыми эффектами из магического камня m_3.
Вы хотите создавать чудесные магические огни для своего мира. Однако, учитывая редкость драгоценных алмазов и ваши предпочтения в последовательностях световых эффектов, вам нужно протестировать свои рецепты крафтинга. Вопрос в том, позволяет ли ваш набор рецептов создать все желаемые последовательности световых эффектов, начиная с магического камня 'A', и какое минимальное количество алмазов потребуется для преобразований.
Входные данные
Первая строка ввода задает количество тестов C (0 < C ≤ 100). Каждый тест начинается с двух целых чисел 0 ≤ R ≤ 30, 0 ≤ L ≤ 10, обозначающих количество рецептов и количество последовательностей световых эффектов. Следующие R строк содержат рецепты. Каждый рецепт задается строкой с магическими камнями m_1, m_2, m_3 и числом d (0 ≤ d ≤ 1000), указывающим количество алмазов, необходимых для преобразования. Следующие L строк содержат последовательности световых эффектов, которые вы хотите создать. Каждая строка начинается с целого числа l (1 ≤ l ≤ 100), обозначающего длину последовательности, и заканчивается строкой длиной l, состоящей только из строчных букв 'a' до 'z', представляющей желаемую последовательность световых эффектов.
Выходные данные
Для каждого теста выведите CASE #, за которым следует номер теста, начиная с 1, в отдельной строке. Для каждой последовательности световых эффектов выведите отдельную строку. Если последовательность возможна, выведите POSSIBLE WITH X DIAMONDS, где X — количество алмазов, необходимых для создания последовательности. Если последовательность создать невозможно, выведите IMPOSSIBLE.