eolymp
Задачі

Хімічні реакції

Хімічні реакції

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

Ваше завдання - написати программу, яка допоможе Біллу. Програма повинна прочитати опис тесту, який складається з лівої частини рівняння і декількох можливих правих частин, і визначити, чи однакова кількість хімічних елементів у кожній запропонованій правій частині рівняння кількості хімічних елементів у заданій лівій частині.

Білл формалізував задачу. І ліва, і права частини рівняня подані рядком символів без пропусків, що складається з однієї або більше хімічних послідовностей, відокремлених знаком плюс. Кожна послідовність має необов'язковий передуючий цілий множник, який відноситься до всієї послідовності, і декілька елементів. Кожен елемент може супроводжуватись необов'язковим цілим множником, шо відноситься до нього. Елемент у цьому рівнянні може бути або окремим хімічним елементом, або цілою послідовністю у круглих дужках. Кожен окремий хімічний елемент подано або однією прописною буквою, або прописною буквою, яка супроводжується рядковою.

Якщо більш формально, використовуючи нотацію, аналогічну формі Бекуса-Наура, можно написати:

<формула>::=[<число>]<послідовність>{"+"[<число>]<послідовність>}

<послідовність>::=<елемент>[<число>]{<елемент>[<число>]}

<елемент>:=<хімічний елемент>|"("<послідовність>")"

<хімічний елемент>::=<прописна буква>[<рядкова буква>]

<прописна буква>::="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 (1N10) - кількість розглядуваних правих частин, у кожному з наступних N рядків - одна формула - пропонована права частина рівняння.

Довжина формули не перевищує 100 символів, кожен окремий хімічний елемент зустрічається всього не більше 10000 разів у кожній формулі.

Вихідні дані

Для кожного із N заданих рядків вивести один рядок виду

<формула лівої частини>==<формула правої частини>

якщо загальна кількість входжень кожного окремого хімічного елемента у ліву частину дорівнює загальній кількості входжень цього хімічного елементу у праву частину. У протилежному випадку виведіть:

<формула лівої частини>!=<формула правої частини>

Тут <формула лівої частини> повинна бути замінена посимвольною копією формули лівої частини, як вона задана у першому рядку вхідного файлу, а <формула правої частини> - замінена точною копією формули правої частини, як вона задана у вхідному файлі. У рядках не повинно бути пропусків.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
C2H5OH+3O2+3(SiO2)
6
2CO2+3H2O+3SiO2
2C+6H+13O+3Si
99C2H5OH+3SiO2
3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)+Ge
3(Si(O)2)+2CO+3H2O+O2
Вихідні дані #1
C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2
C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si
C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2
C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge
C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2