Chemical Reactions

A chemistry teacher has prepared several multiple-choice tests. Each question gives a chemical formula together with a number of candidate answers, and students must pick the one correct reaction outcome. To catch typos, and to stop students from discarding wrong answers simply by counting the atoms on the left and right sides of an equation (which must be equal in any valid reaction), the teacher wants a checker.

Write a program that reads the left-hand side of an equation and a number of candidate right-hand sides, and for each right-hand side decides whether the total count of every distinct chemical element equals the count on the given left-hand side.

Each side of an equation is a string with no spaces, made of one or more sequences separated by +. A sequence may begin with an optional integer multiplier that applies to the whole sequence, followed by one or more elements, where each element may itself be followed by an optional integer multiplier that applies only to that element. An element is either a distinct chemical element or a parenthesized sub-sequence. A distinct chemical element is one uppercase letter, optionally followed by one lowercase letter.

Formally, in BNF-like notation:

<formula>  ::= [<number>] <sequence> { '+' [<number>] <sequence> }
<sequence> ::= <element> [<number>] { <element> [<number>] }
<element>  ::= <chem> | '(' <sequence> ')'
<chem>     ::= <uppercase_letter> [ <lowercase_letter> ]
<uppercase_letter> ::= 'A'..'Z'
<lowercase_letter> ::= 'a'..'z'
<number>   ::= '1'..'9' { '0'..'9' }

A distinct chemical element occurs a total of X times, where X is the sum of every occurrence of that element multiplied by all multipliers that apply to it. For example, in C2H5OH+3O2+3(SiO2):

• C occurs 2 times.
• H occurs 6 times (5 + 1).
• O occurs 13 times (1 + 3×2 + 3×2).
• Si occurs 3 times.

Every explicitly written multiplier is an integer of at least 2; an omitted multiplier is 1. Each formula is at most 100 characters long, and every distinct chemical element occurs at most 10000 times in any formula.

The first line is the chemical formula to test as the left-hand side. The second line contains a single integer N (1 ≤ N ≤ 10), the number of right-hand-side formulas. Each of the next N lines contains one right-hand-side formula.

Print N lines, one for each right-hand-side formula, in input order. For a right-hand-side formula, print

<left_formula>==<right_formula>

if every distinct chemical element occurs the same total number of times on both sides; otherwise print

<left_formula>!=<right_formula>

Here <left_formula> is copied exactly, character by character, from the first input line, and <right_formula> is copied exactly from the corresponding input line. Do not print any spaces.

The sample input and output avoid the digit 0 because it looks like the symbol for the element oxygen (O). Actual tests may contain any allowed character.