Божевільний ветеринар
Mad Veterinarian головоломки представляють божевільного ветеринара, який створив кілька машин, здатних перетворювати одну тварину в одну або більше інших тварин і навпаки. Завдання полягає в тому, щоб з'ясувати, чи можливо перетворити одну колекцію тварин в іншу, використовуючи машини в певному порядку (вперед або назад). Наприклад:
Машина A перетворює одного мурашку в одного бобра.
Машина B перетворює одного бобра в одного мурашку, одного бобра і одного пугу.
Машина C перетворює одного пугу в одного мурашку і одного бобра.
Чи можемо ми перетворити бобра і пугу в 3 мурашки?
Так. {b,c} C → {a,2b} A у зворотному напрямку → {2a,b} A у зворотному напрямку → 3a
Чи можемо ми перетворити одного мурашку в 2 мурашки? НІ
Ці головоломки мають такі властивості:
У прямому режимі кожна машина перетворює одну тварину даного виду в скінченну, не порожню колекцію тварин з видів у головоломці.
Кожна машина може працювати у зворотному напрямку.
Є одна машина для кожного виду в головоломці, і ця машина (у прямому режимі) приймає на вхід одну тварину цього виду.
Напишіть програму, щоб знайти найкоротше рішення (якщо таке є) для головоломок Mad Veterinarian. Для цієї задачі ми обмежимося головоломками Mad Veterinarian з рівно трьома машинами, A, B, C.
Вхідні дані
Перша лінія введення містить одне ціле число P, (1 ≤ P ≤ 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних складається з кількох рядків введення. Кожен набір даних слід обробляти однаково та незалежно.
Перша лінія кожного набору даних складається з двох десяткових цілих чисел, розділених одним пробілом. Перше число - це номер набору даних. Друге число - це кількість, N, питань головоломки. Наступні три рядки введення містять описи машин A, B і C у цьому порядку. Кожен рядок опису машини складається з трьох десяткових цілих чисел, розділених пробілами, що дають кількість тварин типу a, b і c на виході для однієї вхідної тварини. Наступні N рядків містять питання головоломки Mad Veterinarian. Кожен містить сім десяткових цифр, розділених одним пробілом: номер головоломки, три початкові кількості тварин для тварин a, b і c, за якими слідують три бажані кінцеві кількості тварин для тварин a, b і c.
Вихідні дані
Для кожного набору даних введення є кілька рядків виведення. Перший рядок виведення для кожного набору даних містить номер набору даних, пробіл і кількість питань головоломки (N). Для кожного питання головоломки є один рядок виведення, який складається з номера питання головоломки, за яким слідує пробіл, за яким слідує "NO SOLUTION" (без лапок), якщо рішення немає АБО номер питання головоломки, за яким слідує найкоротша кількість кроків машини, пробіл і послідовність літер [A B C a b c] з великими літерами, що вказують на застосування машини в прямому напрямку, і малими літерами, що вказують на застосування машини у зворотному напрямку.