화학 반응식의 균형 맞추기

화학에서 반응식의 양쪽에 있는 각 원자의 개수를 똑같이 맞추는 일, 즉 반응식을 균형 있게 만드는 일은 번거롭지만 꼭 필요한 작업이다. 이 문제는 그 작업을 자동으로 수행하는 프로그램을 작성하는 것이다.

화학자들은 다음 규칙에 따라 화학식을 표기한다.

1. 각 원소의 이름은 많아야 두 글자로 줄여 쓴다. 첫 글자는 항상 대문자이고, 두 번째 글자가 있다면 소문자이다. 예를 들어 칼슘은 Ca, 산소는 O, 염소는 Cl로 쓴다.

2. 하나의 분자는 여러 원자로 이루어진다. 분자를 표기할 때에는 구성 원자들의 약어를 이어 붙인다. 예를 들어 NaCl은 염화 나트륨을 나타낸다. 각 원자 뒤에는 개수를 나타내는 숫자가 올 수 있다. 예를 들어 CaCl2는 칼슘 원자 $1$개와 염소 원자 $2$개로 이루어진다. 개수가 생략되면 $1$로 본다(그래서 HCl은 H1Cl1과 같다). 개수는 항상 $1$부터 $9$까지의 한 자리 숫자이다. 또한 CH3COOH의 수소처럼, 같은 원소가 한 분자식 안에서 여러 번 나타날 수도 있다.

3. 일반적인 화학 반응에서는 여러 분자가 결합하여 다른 여러 분자를 만든다. 잘 알려진 중화 반응의 예는 다음과 같다.

   2HCl + CaO2H2 -> CaCl2 + 2H2O
   

   이는 염산 HCl 분자 $2$개와 수산화 칼슘 CaO2H2 분자 $1$개가 반응하여 염화 칼슘 CaCl2 분자 $1$개와 물 H2O 분자 $2$개를 만든다는 뜻이다.

4. 모든 화학 반응에서, 반응식 오른쪽에 있는 각 원자의 총개수는 왼쪽에 있는 같은 원자의 총개수와 같다. 그래서 이것을 '반응식(등식)'이라 부른다.

균형이 맞지 않는 반응식

$A_1 + A_2 + \cdots + A_M \rightarrow B_1 + B_2 + \cdots + B_N$

이 주어질 때, 다음이 균형을 이루도록 계수 $x_1, x_2, \ldots, x_M$ 과 $y_1, y_2, \ldots, y_N$ 을 찾는 프로그램을 작성하여라.

$x_1 A_1 + x_2 A_2 + \cdots + x_M A_M \rightarrow y_1 B_1 + y_2 B_2 + \cdots + y_N B_N$

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 10$) 가 주어진다. 이어지는 $t$개의 각 줄에는 다음 형태의 반응식이 하나씩 주어진다.

$A_1 + A_2 + \cdots + A_M = B_1 + B_2 + \cdots + B_N$

양쪽 항은 = 로 구분하고, 한쪽 항 안의 분자들은 + 로 구분하며, 각 $A_i$ 와 $B_i$ 는 위 규칙을 따르는 분자식이다.

입력으로 주어지는 반응식은, 만약 균형을 맞출 수 있다면 계수 $x_i$ 와 $y_i$ 를 모두 $1$ 이상 $9$ 이하의 범위에서 정할 수 있도록 보장된다. 한 반응식에 등장하는 분자는 $10$개 미만이고, 서로 다른 원소는 $10$종류 미만이며, 각 분자는 많아야 $3$종류의 서로 다른 원자로 이루어진다. 입력의 각 줄에는 공백 문자가 없고, 길이는 최대 $200$자이다.

각 테스트 케이스마다 한 줄에, 구한 계수들을 다음 순서로 공백 하나로 구분하여 출력한다.

$x_1\ x_2\ \cdots\ x_M\ y_1\ y_2\ \cdots\ y_N$

모든 계수는 $1$ 이상 $9$ 이하의 정수여야 한다. 반응식을 균형 있게 만드는 계수 조합이 여러 가지일 때에는, 계수들을 위 순서대로 이어 붙여 만든 $(M+N)$자리 십진수

$\overline{x_1 x_2 \cdots x_M y_1 y_2 \cdots y_N}$

가 가장 작아지는 조합을 출력한다. 반응식의 균형을 맞추는 것이 불가능하면 IMPOSSIBLE 을 출력한다.