Збалансовані хімічні рівняння
Однією з найбільш складних задач у хімії є балансування кількості атомів у хімічному рівнянні. Наша задача стосується саме цього.
Хіміки дотримуються таких правил при записі хімічних рівнянь:
Назва кожного елемента скорочується до максимум двох літер. Перша літера завжди велика, а друга, якщо є, - мала (наприклад, Кальцій позначається як Ca, Кисень як O, а Хлор як Cl).
Кожна молекула складається з певної кількості атомів. Щоб представити молекулу, ми об'єднуємо скорочені назви її складових атомів. Наприклад, NaCl представляє Хлорид Натрію. Назва кожного атома може супроводжуватися числом частоти. Наприклад, Хлорид Кальцію CaCl2 складається з одного атома Кальцію і двох атомів Хлору. Якщо частота не вказана, вважається, що вона дорівнює 1 (так HCl еквівалентно H1Cl1). Для спрощення, ви можете припустити, що частота появи атома не перевищує 9 (тому ми не маємо C11H22O11 у вхідних даних задачі). Зверніть увагу, що в формулі молекули може бути кілька появ одного й того ж атома, як атом H у CH3COOH.
У звичайних хімічних реакціях кілька молекул об'єднуються і утворюють кілька інших молекул. Наприклад, відомий приклад нейтралізації:
2HCl + CaO2H2 → CaCl2 + 2H2O
Це означає, що дві молекули хлороводневої кислоти (HCl) з однією молекулою Гідроксиду Кальцію утворюють одну молекулу Хлориду Кальцію (CaCl2) і дві молекули води.
У кожній хімічній реакції загальна кількість кожного атома на правій стороні рівняння дорівнює загальній кількості цього атома на лівій стороні (ось чому це називається рівнянням!).
Ваше завдання - написати програму для знаходження відповідних коефіцієнтів x_1, x_2, …, x_{M }і y_1, y_2, …, y_{N }, щоб збалансувати (незбалансоване) рівняння, як
A_1+A_2+A_3+ … +A_M → B_1+B_2+B_3+ … +B_N
таким чином:
x_1 A_1+ x_{2 }A_2+ x_{3 }A_3+ … + x_{M }A_M → y_{1 }B_1+ y_{2 }B_2+ y_{3 }B_3+ … + y_{N }BN
Вхідні дані
Перша строка містить ціле число t (1 ≤ t ≤ 10), кількість тестових випадків. Кожен тестовий випадок складається з одного рядка, що містить вираз, як:
A_1+A_2+A_3+ … +A_{M }= B_1+B_2+B_3+ … +B_N
Кожен A_{i }або B_{i }є формулою молекули згідно з правилами, наведеними в пунктах 1 і 2.
Вхідні рівняння подані таким чином, що якщо їх можна збалансувати, коефіцієнти x_{i }і_{ }y_i_{ }можуть бути в діапазоні від 1 до 9. Існує менше ніж 10 молекул і менше ніж 10 різних типів атомів у даному рівнянні. Крім того, ви можете припустити, що молекули містять не більше ніж 3 різних видів атомів. Ви також можете припустити, що у вхідному файлі немає пробілів, а максимальна довжина вхідних рядків становить 200 символів.
Вихідні дані
Вихід буде містити один рядок на тестовий випадок, що містить список необхідних коефіцієнтів, розділених пробілами, у наступному порядку:
x_{1 } x_{2 } … x_{M } y_{1 } y_{2 } … y_N
Коефіцієнти повинні бути цілими числами в діапазоні від 1..9. Очевидно, що для тестового випадку може бути більше ніж одна відповідь. У таких ситуаціях надрукуйте відповідь, яка мінімізує число:
(Це (M+N)-значне десяткове число, цифрами якого є коефіцієнти x_i і y_i). Якщо рівняння неможливо збалансувати, вихідний рядок повинен бути IMPOSSIBLE.