Божевільний ветеринар#5129

Божевільний ветеринар

1 секунда

32 мегабайти

Складна

Головоломки Mad Veterinarian розповідають про божевільного ветеринара, який винайшов кілька машин для перетворення тварин — одна тварина може стати однією чи кількома тваринами інших видів, і навпаки. Ваше завдання — визначити, чи можна, послідовно застосовуючи ці машини (як у прямому, так і у зворотному порядку), перетворити одну задану кількість тварин на іншу. Наприклад:

Машина A перетворює одного мурашку на одного бобра.

Машина B перетворює одного бобра на одного мурашку, одного бобра та одну пуму.

Машина C перетворює одну пуму на одного мурашку й одного бобра.

Чи можна з бобра і пуми отримати $3$ мурашок?

Так. ${b, c}$ C $\to {a, 2 b}$ \to \{a, 2b\} A (обернено) $\to {2 a, b}$ \to \{2a, b\} A (обернено) $\to 3 a$

Чи можна з одного мурашки отримати двох мурашок? НІ

Ці головоломки мають такі властивості:

У прямому режимі кожна машина перетворює одну тварину певного виду на кінцеву, ненульову кількість тварин (можливо, різних) з тих, які фігурують у задачі.
Кожну машину можна застосувати у зворотному напрямку.
Є рівно одна машина для кожного виду тварин, і ця машина (у прямому режимі) працює, якщо на вході є одна тварина цього виду.

Напишіть програму, яка визначає найкоротшу послідовність застосування машин (якщо така існує), що приводить від початкової кількості тварин до бажаної. У цій задачі розглядаються лише головоломки Mad Veterinarian саме з трьома машинами: A, B, C.

Вхідні дані

У першому рядку міститься одне ціле число $P$ ( $1 \leq P \leq 1000$ 1 \leq P \leq 1000) — кількість тестових наборів. Кожен набір складається з кількох вхідних рядків і розглядається незалежно.

Перший рядок кожного набору містить два цілих числа, розділених пробілом: номер набору та $N$ — кількість запитань у цьому наборі. Далі йдуть три рядки з описом машин A, B, C (у такому ж порядку). Кожен з цих рядків містить по три числа: для кожної машини вказуються, скільки тварин типу $a, b, c$ a, b, c утворюється на виході, якщо на вході була одна тварина відповідного виду.

Кожне з наступних $N$ запитань записане окремим рядком і складається із семи чисел через пробіл: номер запитання, три числа для початкової кількості тварин кожного виду $a, b, c$ a, b, c, і три числа для бажаної (кінцевої) кількості тварин відповідних видів.

Вихідні дані

Виведіть для кожного набору перший рядок: номер набору і $N$ — кількість запитань у цьому наборі. Для кожного запитання виведіть один рядок, що містить: номер запитання, пробіл і NO SOLUTION, якщо розв'язку не існує; АБО номер запитання, мінімальну кількість кроків машин, пробіл і послідовність літер [A B C a b c], де великі літери означають застосування машини у прямому напрямку, а малі — у зворотному.

Приклади

Приклад 1