화학 반응식

화학 교사가 여러 개의 객관식 시험을 준비했다. 각 문항은 화학식 하나와 여러 개의 후보 답을 제시하며, 학생은 그중 올바른 반응 결과 하나를 골라야 한다. 오타를 잡아내고, 또 학생들이 반응식 좌변과 우변의 원자 개수(올바른 반응이라면 항상 같아야 한다)만 세어 오답을 손쉽게 걸러내지 못하도록, 교사는 검사기를 원한다.

좌변 화학식 하나와 여러 개의 우변 후보 화학식이 주어질 때, 각 우변에 대해 모든 화학 원소의 총 개수가 주어진 좌변의 총 개수와 같은지 판정하는 프로그램을 작성하라.

반응식의 각 변은 공백이 없는 문자열이며, + 로 구분된 하나 이상의 열(sequence)로 이루어진다. 각 열은 열 전체에 적용되는 정수 배수로 시작할 수 있고(선택적), 그 뒤에 하나 이상의 원소가 이어지며, 각 원소 뒤에는 그 원소에만 적용되는 정수 배수가 선택적으로 붙을 수 있다. 하나의 원소(element)는 개별 화학 원소이거나 괄호로 묶인 부분 열이다. 개별 화학 원소는 대문자 한 글자이며, 그 뒤에 소문자 한 글자가 선택적으로 붙는다.

BNF 형태로 형식화하면 다음과 같다.

<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' }

어떤 화학 원소의 총 개수 X는, 그 원소가 등장할 때마다 그 원소에 적용되는 모든 배수를 곱한 값을 전부 더한 값이다. 예를 들어 C2H5OH+3O2+3(SiO2) 에서:

• C는 총 2번.
• H는 총 6번 (5 + 1).
• O는 총 13번 (1 + 3×2 + 3×2).
• Si는 총 3번.

명시적으로 적힌 배수는 모두 2 이상의 정수이며, 생략된 배수는 1이다. 각 화학식의 길이는 최대 100자이고, 각 화학 원소는 하나의 화학식에서 최대 10000번 등장한다.

첫째 줄에는 좌변으로 검사할 화학식이 주어진다. 둘째 줄에는 우변 화학식의 개수 N (1 ≤ N ≤ 10)이 주어진다. 이어지는 N개의 줄에는 각각 하나의 우변 화학식이 주어진다.

우변 화학식마다 한 줄씩, 입력 순서대로 N개의 줄을 출력한다. 각 우변 화학식에 대해, 두 변에서 모든 화학 원소의 총 등장 횟수가 같으면

<left_formula>==<right_formula>

을, 그렇지 않으면

<left_formula>!=<right_formula>

을 출력한다. 여기서 <left_formula>는 입력 첫째 줄의 좌변 화학식을, <right_formula>는 해당 우변 화학식을 각각 글자 그대로 복사한 것이다. 공백은 출력하지 않는다.

예제 입력과 출력에는 숫자 0이 나오지 않는데, 산소 원소 기호 O와 모양이 비슷하기 때문이다. 실제 테스트에는 허용된 어떤 문자든 나올 수 있다.