Магічне ремесло#6547
Одна з найяскравіших інді-ігор останніх років — Minecraft, захоплива гра, у якій ви видобуваєте матеріали та майструєте з них різноманітні речі. Після опанування всесвіту Minecraft ви вирішили написати власний мод до гри, щоб додати магічне ремесло.
Маючи магічний камінь m_1, додавши певну кількість алмазів, ви можете перетворити його на два магічні камені m_2 і m_3, де m_1, m_2 і m_3 — це великі літери. Таке перетворення називається рецептом створення.
Існує і стандартне перетворення, яке перетворює магічний камінь на відповідний світловий ефект; відповідний світловий ефект для магічного каменя з великої літери — це відповідна мала літера, наприклад, магічний камінь 'A' можна перетворити на світловий ефект 'a'. Це перетворення завжди коштує рівно алмаз. Стандартне перетворення використовується, якщо магічний камінь не використано в іншому рецепті створення. Світлові ефекти зʼявляються у певному порядку. Для кожного використаного рецепта створення m_1 \rightarrow m_2 m_3 ефекти, що походять від каменя m_2, будуть показані раніше, ніж ефекти від каменя m_3.
Ви хочете створити чудові магічні вогні для свого світу. Але, враховуючи рідкісність дорогоцінних алмазів і прискіпливість до послідовностей світлових ефектів, які ви прагнете отримати, вам слід перевірити власні рецепти створення. Постає питання: чи дозволяє ваш набір рецептів виготовлення створити всі бажані послідовності світлових ефектів, якщо почати тільки з магічного каменя 'A', і яка мінімальна кількість алмазів потрібна для перетворень.
Перший рядок містить кількість тестових випадків (0 < C \leq 100). Кожен тестовий випадок починається з двох цілих чисел та (0 \leq R \leq 30, 0 \leq L \leq 10) в одному рядку — кількість рецептів і кількість послідовностей світлових ефектів. Далі подано рядків, кожен містить рецепт: магічні камені m_1, m_2, m_3 і число (0 \leq d \leq 1000), що означає кількість алмазів, потрібних для перетворення. У наступних рядках подано послідовності світлових ефектів, які ви хочете створити. Кожен із цих рядків містить ціле число (1 \leq l \leq 100), що визначає довжину послідовності, та рядок довжини з малих літер від 'a' до 'z', що є бажаною послідовністю світлових ефектів.
Для кожного тестового випадку виведіть у окремому рядку CASE #, після якого йде номер тесту, починаючи з . Для кожної послідовності ефектів виведіть новий рядок. Якщо послідовність можлива, виведіть POSSIBLE WITH DIAMONDS, де — кількість алмазів, необхідних для отримання відповідної послідовності. Якщо послідовність світлових ефектів створити неможливо, виведіть IMPOSSIBLE.
Приклад 1