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