Збалансовані хімічні рівняння#6846
Однією з найбільш складних задач у хімії є балансування кількості атомів у хімічному рівнянні. Наша задача стосується саме цього.
Хіміки дотримуються таких правил при записі хімічних рівнянь:
Назва кожного елемента скорочується до максимум двох літер. Перша літера завжди велика, а друга, якщо є, - мала (наприклад, Кальцій позначається як Ca, Кисень як O, а Хлор як Cl).
Кожна молекула складається з певної кількості атомів. Щоб представити молекулу, ми об'єднуємо скорочені назви її складових атомів. Наприклад, NaCl представляє Хлорид Натрію. Назва кожного атома може супроводжуватися числом частоти. Наприклад, Хлорид Кальцію CaCl2 складається з одного атома Кальцію і двох атомів Хлору. Якщо частота не вказана, вважається, що вона дорівнює (так HCl еквівалентно H1Cl1). Для спрощення, ви можете припустити, що частота появи атома не перевищує (тому ми не маємо C11H22O11 у вхідних даних задачі). Зверніть увагу, що в формулі молекули може бути кілька появ одного й того ж атома, як атом H у CH3COOH.
У звичайних хімічних реакціях кілька молекул об'єднуються і утворюють кілька інших молекул. Наприклад, відомий приклад нейтралізації:
2HCl + CaO2H2 → CaCl2 + 2H2O
Це означає, що дві молекули хлороводневої кислоти (HCl) з однією молекулою Гідроксиду Кальцію утворюють одну молекулу Хлориду Кальцію (CaCl2) і дві молекули води.
У кожній хімічній реакції загальна кількість кожного атома на правій стороні рівняння дорівнює загальній кількості цього атома на лівій стороні (ось чому це називається рівнянням!).
Ваше завдання - написати програму для знаходження відповідних коефіцієнтів x_1, x_2, \ldots, x_M і y_1, y_2, \ldots, y_N, щоб збалансувати (незбалансоване) рівняння, як
таким чином:
Перший рядок містить ціле число (1 \le t \le 10), кількість тестових випадків. Кожен тестовий випадок складається з одного рядка, що містить вираз, як:
Кожен A_i або B_i є формулою молекули згідно з правилами, наведеними в пунктах і .
Вхідні рівняння подані таким чином, що якщо їх можна збалансувати, коефіцієнти x_i і y_i можуть бути в діапазоні від до . Існує менше ніж молекул і менше ніж різних типів атомів у даному рівнянні. Крім того, ви можете припустити, що молекули містять не більше ніж різних видів атомів. Ви також можете припустити, що у вхідному файлі немає пробілів, а максимальна довжина вхідних рядків становить символів.
Вихід буде містити один рядок на тестовий випадок, що містить список необхідних коефіцієнтів, розділених пробілами, у наступному порядку:
Коефіцієнти повинні бути цілими числами в діапазоні від до . Очевидно, що для тестового випадку може бути більше ніж одна відповідь. У таких ситуаціях надрукуйте відповідь, яка мінімізує число:
(Це (M+N)-значне десяткове число, цифрами якого є коефіцієнти x_i і y_i). Якщо рівняння неможливо збалансувати, вихідний рядок повинен бути IMPOSSIBLE.
Приклад 1