Хімічні реакції
Білл викладає хімію у школі, він підготовував декілька тестів для учнів. Кожен тест складається з хімічної формули і декількох можливих результатів реакції. Серед цих результатів учні повинні вибрати вірний. Білл хоче переконатись у тому, що при введенні своїх тестів у комп'ютер, він не допустив помилок, завдяки яким учні могли б відкинути невірні відповіді, просто підрахувавши кількості хімічних елементів і лівій та правій частинах рівняння (у вірних рівняннях хімічних реакцій повинна зберігатись рівність).
Ваше завдання - написати программу, яка допоможе Біллу. Програма повинна прочитати опис тесту, який складається з лівої частини рівняння і декількох можливих правих частин, і визначити, чи однакова кількість хімічних елементів у кожній запропонованій правій частині рівняння кількості хімічних елементів у заданій лівій частині.
Білл формалізував задачу. І ліва, і права частини рівняня подані рядком символів без пропусків, що складається з однієї або більше хімічних послідовностей, відокремлених знаком плюс. Кожна послідовність має необов'язковий передуючий цілий множник, який відноситься до всієї послідовності, і декілька елементів. Кожен елемент може супроводжуватись необов'язковим цілим множником, шо відноситься до нього. Елемент у цьому рівнянні може бути або окремим хімічним елементом, або цілою послідовністю у круглих дужках. Кожен окремий хімічний елемент подано або однією прописною буквою, або прописною буквою, яка супроводжується рядковою.
Якщо більш формально, використовуючи нотацію, аналогічну формі Бекуса-Наура, можно написати:
<формула>::=[<число>]<послідовність>{"+"[<число>]<послідовність>}
<послідовність>::=<елемент>[<число>]{<елемент>[<число>]}
<елемент>:=<хімічний елемент>|"("<послідовність>")"
<хімічний елемент>::=<прописна буква>[<рядкова буква>]
<прописна буква>::="A".."Z"
<рядкова буква>::="a".."z"
<число>::="1".."9"{"0".."9"}
Будемо казати, що кожен окремий хімічний елемент зустрічається у формулі всього X разів, якщо X - сума всіх різних входжень цього хімічного елементу, помножена на всі числа, що відносяться до них. Наприклад у формулі C2H5OH+3O2+3(SiO2)
C зустрічається всього 2 рази;
H зустрічається всього (5+1) разів;
O зустрічається всього 13 разів (1+3·2+3·2);
Si зустрічається всього 3 рази.
Усі множники у формулах - цілі числа, не менші 2, якщо задані явно, або рівні 1 - по замовчуванню.
Вхідні дані
У першому рядку знаходиться формула - ліва частина рівняння, у другому - одне число N (1 ≤ N ≤ 10) - кількість розглядуваних правих частин, у кожному з наступних N рядків - одна формула - пропонована права частина рівняння.
Довжина формули не перевищує 100 символів, кожен окремий хімічний елемент зустрічається всього не більше 10000 разів у кожній формулі.
Вихідні дані
Для кожного із N заданих рядків вивести один рядок виду
<формула лівої частини>==<формула правої частини>
якщо загальна кількість входжень кожного окремого хімічного елемента у ліву частину дорівнює загальній кількості входжень цього хімічного елементу у праву частину. У протилежному випадку виведіть:
<формула лівої частини>!=<формула правої частини>
Тут <формула лівої частини> повинна бути замінена посимвольною копією формули лівої частини, як вона задана у першому рядку вхідного файлу, а <формула правої частини> - замінена точною копією формули правої частини, як вона задана у вхідному файлі. У рядках не повинно бути пропусків.