Description

A chemical equation is an expression that connects several chemical substances with plus signs (+) and an equals sign (=). It is guaranteed that a chemical equation contains exactly one equals sign (=). A chemical substance is formed by several elements (denoted by uppercase letters A to Z) concatenated with subscripts (subscripts are non-negative integers not exceeding $9$). For example: JQY2, A0J1QY2. When writing, you must ensure that letters with smaller lexicographic order appear earlier.

Note that a substance like A0J1QY2 is also valid, although it is in fact equivalent to JQY2. We call elements with subscript $1$ “unit elements”, and elements with subscript $0$ “null elements”. When writing a substance, you may omit the subscript of “unit elements”, and you may directly omit “null elements”. In particular, we call the writing minimized by these two rules the “minimal form” of the substance. For example, JQY2 is the minimal form of A0J1Q1Y2.

Since it is called an “equation”, conservation of elements is required. For a chemical equation, conservation of elements means the sums of subscripts of all elements on the two sides of the equals sign are equal. For example, this chemical equation conserves elements:

JQY2+J2=J3QY2

This chemical equation is invalid because it does not satisfy conservation of elements:

JQY2+J2=JQY

As a seasoned alchemist, Yazid is naturally obsessed with chemical rampage all day long. One day, Yazid wrote down $n$ chemical equations and set them aside for later research.

However, the apprentice alchemist YJQQQAQ accidentally knocked over a bottle of green reagent, causing exactly $1$ substance in each of Yazid’s chemical equations to be blurred.

The enraged Yazid harshly criticized YJQQQAQ and demanded that he rewrite all the blurred substances. Moreover, as punishment, regardless of how Yazid originally wrote those substances, YJQQQAQ must write them in their “minimal form”.

If he cannot complete these tasks, Yazid will banish him from the Qinqin Grassland. Faced with so many chemical equations, the weak and helpless YJQQQAQ was at a loss, so he found you, the best programmer in the Qinqin Grassland, to help him complete the task.

Input Format

Read from standard input.

The first line contains $2$ integers $n, m$, representing the number of chemical equations and Yazid’s writing habit, respectively. The writing habit $m$ is an integer from $0$ to $3$. For different $m$, Yazid writes substances differently (this information may help you on some test points):

If $m=0$, then when writing equations, Yazid will always reduce all substances to their “minimal form”.

If $m=1$, then when writing equations, Yazid will always omit all “null elements”, and the subscripts of “unit elements” will not be omitted.

If $m=2$, then when writing equations, Yazid will always omit the subscripts of all “unit elements”, and no “null elements” will be omitted.

If $m=3$, then when writing equations, Yazid will neither omit the subscripts of “unit elements” nor omit “null elements”.

The next $n$ lines each contain one string describing a polluted chemical equation. The blurred substance is denoted by ?, and it is guaranteed that for each equation there is exactly $1$ ?.

The testdata guarantees that chemical equations strictly follow the format described in the Background and Description, and there are no extra spaces or other characters.

Output Format

Output to standard output.

Output $n$ lines, each containing a string that is the “minimal form” of the substance represented by ?. In particular, for cases with no solution (i.e., the substance represented by ? is beyond the scope of the chemistry discipline of the Qinqin Grassland), output No Solution.

3 0
A=?
?=A+B
C+O2=?

A
AB
CO2

3 1
A1=?
A1+?=B1
C1+O2=?

A
No Solution
CO2

1 2
A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0=?

JQY2

2 3
?=A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0
A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0+A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0=?

JQY2
J2Q2Y4

Hint

If “? at the very left” is Yes in the table, then each string in that testpoint is guaranteed to have ? as its first character; otherwise there is no special guarantee.

If “No + on the left of =” is Yes in the table, then each testpoint is guaranteed to have no plus sign (+) on the left side of the equals sign, i.e., there is only one substance on the left; otherwise there is no special guarantee.

If “No + on the right of =” is Yes in the table, then each testpoint is guaranteed to have no plus sign (+) on the right side of the equals sign, i.e., there is only one substance on the right; otherwise there is no special guarantee.

For all test points, it is guaranteed that $n \le 100$, and the number of plus signs (+) on each side of the equation does not exceed $5$. This also implies that the length of each line (each chemical equation) does not exceed $635$.

From CodePlus 2017 December Contest, proudly presented by the Student Algorithms and Competition Association of the Department of Computer Science and Technology, Tsinghua University.

Credit: idea/Wang Yuzhong, problem setting/Wang Yuzhong, verification/Chen Yu.

Git Repo: https://git.thusaac.org/publish/CodePlus201712

Thanks to Tencent for supporting this contest.

Thanks to

Translated by ChatGPT 5