P4029 [Code+#2] Chemical Rampage

In the distant Qinqin Grassland, Yazid and YJQQQAQ live there as alchemists. In general, problem backgrounds are often useless, but this one is an exception. Here, we will rigorously introduce some basic knowledge of the chemistry discipline in the world of the Qinqin Grassland. If you find this content tedious, you may skip it and directly read the brief description in the problem statement and the samples to help you understand the problem more quickly. There are $26$ kinds of elements in the world of the Qinqin Grassland, denoted by uppercase letters A to Z. Substances in the Qinqin Grassland are composed of elements. For any substance, the occurrence count of each element is a non-negative integer, and at least one element has a positive count. We call the occurrence count of each element in a substance the subscript (index) of that element in that substance. We can write down each element and its subscript in the order from A to Z to describe a substance. Here is an example: `A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0`. This example describes a substance where J and Q each appear $1$ time, and Y appears $2$ times. However, this way of describing is too cumbersome, so the alchemists in the Qinqin Grassland tried to simplify substance descriptions. For a given substance, we define “null elements” as elements with subscript $0$ in this substance, and “unit elements” as elements with subscript $1$ in this substance. Based on these two definitions, the alchemists proposed two simplification methods: Omit “null elements”: remove the letters and subscripts of “null elements”. The substance above can be simplified to: `J1Q1Y2`. Omit the subscripts of “unit elements”: remove the subscripts of “unit elements”. The substance above can be simplified to: `A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0`. In particular, when both the “null elements” and the subscripts of “unit elements” are omitted, we call it the “minimal form” of the substance. For the substance above, its “minimal form” is: `JQY2`. Since the chemical research in the Qinqin Grassland is still in its infancy, for any substance, all element subscripts are non-negative integers not exceeding $9$. A chemical equation describes a chemical reaction. A chemical equation contains exactly one equals sign (=), and each side of the equals sign is a number of substances connected by plus signs (+). Informally, it looks like this: ``` Substance+Substance+…+Substance=Substance+Substance+…+Substance ``` In addition to satisfying the above format, conservation of elements must not be ignored. This means the total occurrence counts of all elements on both sides of the equals sign must be equal across all substances. For example, this is a valid (format-correct and element-conserving) chemical equation: ``` JQY2+J2=J3QY2 ``` It is especially important to note that, in writing chemical equations, elements not reduced to the “minimal form” are also acceptable. For example, the following chemical equation is also valid: ``` J1Q1Y2+J2=J3Q1Y2 ``` However, the following chemical equation is not valid, because it does not satisfy conservation of elements. ``` JQY2+J2=JQY ``` That concludes the basic knowledge of chemistry in the Qinqin Grassland. Good luck to all contestants!

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.

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 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`.

|Testpoint ID|m|? at the very left|No + on the left of =|No + on the right of =| |:-:|:-:|:-:|:-:|:-:| |1|0|Yes|Yes|Yes| |2|1|Yes|Yes|Yes| |3|2|Yes|Yes|Yes| |4|3|Yes|Yes|Yes| |5|0|Yes|Yes|| |6|1|Yes|Yes|| |7|2|Yes|Yes|| |8|3|Yes|Yes|| |9|0|Yes||Yes| |10|1|Yes||Yes| |11|2|Yes||Yes| |12|3|Yes||Yes| |13|0|||| |14|1|||| |15|2|||| |16|3|||| |17|0|||| |18|1|||| |19|2|||| |20|3||| 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](https://git.thusaac.org/publish/CodePlus201712) Thanks to Tencent for supporting this contest. Thanks to @[ChampionCyan](https://www.luogu.com.cn/user/1036180) for providing the fixed statement. Translated by ChatGPT 5