Background

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!

Problem 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

Testpoint ID	m	? at the very left	No + on the left of =	No + on the right of =
1	0	Yes	Yes	Yes
2	1
3	2
4	3
5	0
6	1
7	2
8	3
9	0			Yes
10	1
11	2
12	3
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

Thanks to Tencent for supporting this contest.

Thanks to

ing the fixed statement.

Translated by ChatGPT 5