Problem Background

In the distant QinQin Grassland, there live Yazid and YJQQQAQ, both of whom are alchemists.

Generally, the problem background is useless, but this problem is an exception. Here, we will rigorously introduce some basic knowledge of chemistry in the QinQin Grassland world. If you find this content dry and boring, you can skip this part, read the brief description in the problem statement, and use the examples to help you understand the problem more quickly.

In the QinQin Grassland world, there are 26 elements, represented by uppercase letters A to Z.

In the QinQin Grassland world, substances 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 integer occurrence count. We call the occurrence count of each element in the substance its subscript. We can describe a substance by writing down each element and its subscript in the order from A to Z. Here is an example: A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0. This example describes a substance where J and Q each appear once, and Y appears twice.

However, this description method is too cumbersome, so the alchemists in the QinQin Grassland world tried to simplify the description of substances. For a substance, we define "null elements" as elements with a subscript of 0 and "single elements" as elements with a subscript of 1. Based on these definitions, the alchemists proposed two simplification methods:

1. Omit "null elements": Omit the letters and subscripts of "null elements". For example, the above substance can be simplified to: J1Q1Y2.
2. Omit the subscripts of "single elements": Omit the subscripts of "single elements". For example, the above substance can be simplified to: A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0.

Particularly, for a representation that omits both "null elements" and the subscripts of "single elements", we call it the "simplest form" of the substance. For example, the "simplest form" of the above substance is: JQY2.

Since the chemical research in the QinQin Grassland world is still in its infancy, for any substance, all element subscripts are non-negative integers not exceeding 9.

A chemical equation is a formula that describes a chemical reaction. A chemical equation contains exactly one equal sign (=), and both sides of the equal sign are connected by plus signs (+) with several substances. Visually, it looks like this:

substance+substance+…+substance=substance+substance+…+substance

In addition to needing to satisfy the above format, element conservation is also indispensable. This means that the total occurrence count of all elements in each substance on both sides of the equal sign must be equal. For example, this is a valid (format correct, element conservation) chemical equation:

JQY2+J2=J3QY2

It is important to note that in the writing of chemical equations, elements that are not reduced to the "simplest form" are also acceptable. For example, the following chemical equation is also valid:

JQY2+J2=JQY

And this chemical equation is not valid because it does not satisfy element conservation.

JQY2+J2=JQY

The basic knowledge of chemistry in the QinQin Grassland world is introduced here. Good luck to all contestants!

Problem Description

A chemical equation is a formula that connects some chemical substances with plus signs (+) and an equal sign (=). It is guaranteed that a chemical equation contains exactly one equal sign (=). Chemical substances are composed of some elements (represented by uppercase letters A to Z) with subscripts (guaranteed to be non-negative integers not exceeding 9). For example: JQY2, A0J1QY2, etc. When writing, it is necessary to ensure that letters with smaller lexicographical order come first.

It is important to note that a substance like A0J1QY2 is also a valid writing, even though it is equivalent to JQY2. We call elements with a subscript of 1 "single elements" and elements with a subscript of 0 "null elements". When writing a substance, we can either omit the subscripts of "single elements" or directly omit "null elements". Particularly, we call the most simplified writing using these two rules the "simplest form" of the substance. For example, JQY2 is the simplest form of A0J1Q1Y2.

Since it is called an "equation," element conservation is a must. For a chemical equation, element conservation means that the sum of the subscripts of all elements on both sides of the equal sign is equal. For example, this chemical equation is element-conserving:

JQY2+J2=J3QY2

And this chemical equation is not valid because it does not satisfy element conservation:

JQY2+J2=JQY

As a senior alchemist, Yazid is naturally obsessed with chemical frenzy. One day, Yazid wrote down n chemical equations and left them aside for subsequent research.

However, the apprentice alchemist YJQQQAQ accidentally spilled a green reagent, causing exactly one substance in each of Yazid's written chemical equations to become blurred.

Enraged, Yazid severely criticized YJQQQAQ and demanded that he rewrite all the blurred substances. In addition, as a punishment, regardless of how Yazid originally wrote these substances, YJQQQAQ must write them in their "simplest form".

If he cannot complete these tasks, Yazid will exile him from QinQin Grassland. Faced with so many chemical equations, the helpless YJQQQAQ has no idea what to do, so he turns to you, the best programmer in QinQin Grassland, for help.

Input Format

Read data from standard input.

The first line contains 2 integers n and m, representing the number of chemical equations and Yazid's writing habits, respectively. Yazid's writing habit m is an integer between 0 and 3. For different m, Yazid's way of writing substances varies (this information may be helpful for solving some test cases):

• If m=0, Yazid always writes all substances in their "simplest form".
• If m=1, Yazid always omits "null elements" and never omits the subscripts of "single elements".
• If m=2, Yazid always omits the subscripts of "single elements" and never omits "null elements".
• If m=3, Yazid never omits the subscripts of "single elements" and never omits "null elements".

Next, n lines follow, each containing a string describing a contaminated chemical equation. The contaminated substance is represented by ?. It is guaranteed that there is exactly one ? in each equation.

The data guarantees that the chemical equations strictly follow the format in the problem background and description, and there are no extra spaces or characters.

Output Format

Output to standard output.

Output n lines, each containing a string representing the substance represented by ? in its "simplest form". In particular, for cases where there is no solution (i.e., the substance represented by ? exceeds the scope of chemical research in the QinQin Grassland world), output No Solution.

Sample Input and Output

Input Sample #1

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

Output Sample #1

A
AB
CO2

Input Sample #2

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

Output Sample #2

A
No Solution
CO2

Input Sample #3

1 2
A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0=?

Output Sample #3

JQY2

Input Sample #4

2 3
?=A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0
A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0+A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0=?

Output Sample #4

JQY2
J2Q2Y4

Notes/Hints

If "? at the leftmost end" is Yes in the table, it means that the test case guarantees that the first character of each string is ?; otherwise, there is no special guarantee.

If "No + on the left side of the equal sign" is Yes in the table, it means that the test case guarantees that there is no plus sign (+) on the left side of the equal sign, i.e., there is only one substance on the left side of the equal sign; otherwise, there is no special guarantee.

If "No + on the right side of the equal sign" is Yes in the table, it means that the test case guarantees that there is no plus sign (+) on the right side of the equal sign, i.e., there is only one substance on the right side of the equal sign; otherwise, there is no special guarantee.

For all test cases, it is guaranteed that $n \leq 100$, and the number of plus signs (+) on both sides of the equation in each equation does not exceed 5, which means the length of each string (each chemical equation) does not exceed 635.

From CodePlus December 2017, hosted by the Student Algorithm and Competition Association of the Department of Computer Science and Technology, Tsinghua University.

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

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

Thanks to Tencent for supporting this competition.

Thanks to @ChampionCyan for providing the repaired problem statement.

见题面 Input 部分

见题面 Output 部分