Химические реакции
Билл преподает химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильных уравнениях химической реакции должно соблюдаться равенство).
Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализировал задачу. И левая, и правая части уравнения представляется строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделенных знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательность в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Если более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:
<формула>::=[<число>]<последовательность>{"+"[<число>]<последовательность>}
<последовательность>::=<элемент>[<число>]{<элемент>[<число>]}
<элемент>:=<химический элемент>|"("<последовательность>")"
<химический элемент>::=<прописная буква>[<строчная буква>]
<прописная буква>::="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 заданных строк вывести одну строку вида
<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть заменена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> - замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.