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

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

Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.

Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:

• <формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
• <последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
• <элемент> ::= <химический элемент> | "(" <последовательность> ")"
• <химический элемент> ::= <прописная буква> [<строчная буква>]
• <прописная буква> ::= "A".."Z"
• <строчная буква> ::= "a".."z"
• <число> ::= "1".."9" {"0".."9"}

Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)

• C встречается всего 2 раза;
• H встречается всего 6 раз (5 + 1);
• O встречается всего 13 раз; (1 + 3 * 2 + 3 * 2);
• Si встречается всего 3 раза.

Все множители в формулах - целые числа не меньше 2, если заданы явно, или равны 1 - по умолчанию.

По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.

Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000.

Дан набор переменных x₁, x₂, ..., x_N. Каждая переменная x_i может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным x_i значения так, чтобы сумма всех возможных произведений x_i * x_j была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число x_i = 0.

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

• Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.

Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.

Ограничения: длина исходной последовательности от 1 до 100.

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

Ограничения: длины рёбер - целые положительные числа, не превосходящие 1000.