Магічне Ремесло
Одна з останніх популярних незалежних ігор — це 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.