A6431. 「CodePlus 2017 12 月赛」化学狂暴
编程题
普及+/提高
知识点
题目描述
在那遥远的钦钦草原，住着 Yazid 和 YJQQQAQ，他们都是炼金术士。
一般而言，题目背景总是没有用的，但这道题是个例外。在这里，我们将**严谨地**介绍钦钦草原世界化学学科的一些基本知识。如果你对这些内容感到枯燥乏味，你也可以跳过这个部分，直接阅读「题目描述」中的简述并结合「样例」来帮助你更快地理解题目。
钦钦草原的世界里共有 $26$ 种**元素**，分别用大写字母
钦钦草原世界中的**物质**由元素构成，对于任意的物质，每种元素的出现次数都是非负整数，且至少有 $1$ 种物质的出现次数为正整数，我们把每种元素在物质中的出现次数称作该元素在该物质中的**下标**。我们可以按
然而，这种描述方法实在是太麻烦了，于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质，我们定义“虚无元素”表示在该物质中下标为 $0$ 的元素，“单一元素”表示在该物质中下标为 $1$ 的元素。针对这两个定义，炼金术士们提出了两种化简方式：
* 省略“虚无元素”：将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为：
* 省略“单一元素”的下标：将“单一元素”的下标省略。如上面的物质可以通过该操作化简为：
特别地，对于同时省略了“虚无元素”和“单一元素”下标的表示，我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为：
**由于钦钦草原世界的化学研究仍处于起步阶段，因此对于任意的物质，所有元素下标均为不超过 $9$ 的非负整数。**
**化学方程式**是描述化学反应的式子。一个化学方程式包含恰好一个等号（
```plain
物质+物质+…+物质=物质+物质+…+物质
```
除了需要满足上述格式外，元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如，这就是一个合法的（格式正确、元素守恒的）化学方程式：
```plain
JQY2+J2=J3QY2
```
需要特别注意的是，在化学方程式的书写中，未被化至“最简式”的元素也是可以被接受的。例如，下面的化学方程式也是合法的：
```plain
J1Q1Y2+J2=J3Q1Y2
```
而下面这个化学方程式就不是合法的了，因为它并没有满足元素守恒。
```plain
JQY2+J2=JQY
```
钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆！
<hr style='color: #ddd; margin-bottom: 1em'>
所谓化学方程式，即是用加号（
需要注意的是，像
既然称之为“方程式”，元素守恒就是必须的了。对于一个化学方程式，元素守恒指的是指等号两边所有元素的下标之和相等。比如，这个化学方程式就是元素守恒的：
```plain
JQY2+J2=J3QY2
```
而这个化学方程式就是不合法的，因为它不满足元素守恒：
```plain
JQY2+J2=JQY
```
作为一名资深炼金术士，Yazid 自然是整日沉迷在化学狂暴中。某一天，Yazid 写下了 $n$ 个化学方程式，并把它们放在一边，为后续的研究做着准备。
然而，见习炼金术士 YJQQQAQ 不慎打翻了一瓶绿色的试剂，导致 Yazid 写下的所有化学方程式中，都有**恰好** $1$ 个物质被绿色液体弄得模糊不清了。
暴怒的 Yazid 狠狠地把 YJQQQAQ 批判了一番，并要求他将所有模糊不清的物质重新写出来。除此之外，作为惩罚，**无论原来 Yazid 如何书写这些物质，YJQQQAQ 都必须将它们以“最简式”的形式写出**。
如果不能完成这些任务，Yazid 就会把他从钦钦草原放逐。面对这么多的化学方程式，弱小、无助的 YJQQQAQ 手足无措，于是他找到了钦钦草原最擅长编程的你，请你帮他完成任务。
一般而言，题目背景总是没有用的，但这道题是个例外。在这里，我们将**严谨地**介绍钦钦草原世界化学学科的一些基本知识。如果你对这些内容感到枯燥乏味，你也可以跳过这个部分，直接阅读「题目描述」中的简述并结合「样例」来帮助你更快地理解题目。
钦钦草原的世界里共有 $26$ 种**元素**，分别用大写字母
A 至 Z 表示。钦钦草原世界中的**物质**由元素构成，对于任意的物质，每种元素的出现次数都是非负整数，且至少有 $1$ 种物质的出现次数为正整数，我们把每种元素在物质中的出现次数称作该元素在该物质中的**下标**。我们可以按
A 到 Z 的顺序写下每种元素及其下标来描述一个物质。这是一个例子：A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0。这个例子描述了一种 J、Q 各出现 $1$ 次，Y 出现 $2$ 次的物质。然而，这种描述方法实在是太麻烦了，于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质，我们定义“虚无元素”表示在该物质中下标为 $0$ 的元素，“单一元素”表示在该物质中下标为 $1$ 的元素。针对这两个定义，炼金术士们提出了两种化简方式：
* 省略“虚无元素”：将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为：
J1Q1Y2。* 省略“单一元素”的下标：将“单一元素”的下标省略。如上面的物质可以通过该操作化简为：
A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0。特别地，对于同时省略了“虚无元素”和“单一元素”下标的表示，我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为：
JQY2。**由于钦钦草原世界的化学研究仍处于起步阶段，因此对于任意的物质，所有元素下标均为不超过 $9$ 的非负整数。**
**化学方程式**是描述化学反应的式子。一个化学方程式包含恰好一个等号（
=），等号两边是由加号（+）连接的若干物质。形象地说，它的形式是这样的：```plain
物质+物质+…+物质=物质+物质+…+物质
```
除了需要满足上述格式外，元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如，这就是一个合法的（格式正确、元素守恒的）化学方程式：
```plain
JQY2+J2=J3QY2
```
需要特别注意的是，在化学方程式的书写中，未被化至“最简式”的元素也是可以被接受的。例如，下面的化学方程式也是合法的：
```plain
J1Q1Y2+J2=J3Q1Y2
```
而下面这个化学方程式就不是合法的了，因为它并没有满足元素守恒。
```plain
JQY2+J2=JQY
```
钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆！
<hr style='color: #ddd; margin-bottom: 1em'>
所谓化学方程式，即是用加号（
+）和等号（=）连接一些化学物质的式子。保证一个化学方程式中含有**恰好**一个等号（=）。化学物质由一些元素（用大写字母 A 至 Z 表示）加上下标（保证下标为不超过$9$的非负整数）连接而成的。例如：JQY2、A0J1QY2 等。书写时需要保证字典序越小的字母排在越前面。需要注意的是，像
A0J1QY2 这样的物质书写同样是合法的，虽然事实上它和 JQY2 是等价的。我们把下标为 $1$ 的元素称为“单一元素”，把下标为 $0$ 的元素称为“虚无元素”。在书写一种物质时，我们既可以省去“单一元素”的下标，又可以直接省去“虚无元素”。特别地，我们把用这两种规则省略至最简的书写称为该物质的“最简式”。例如，JQY2 就是 A0J1Q1Y2 的最简式。既然称之为“方程式”，元素守恒就是必须的了。对于一个化学方程式，元素守恒指的是指等号两边所有元素的下标之和相等。比如，这个化学方程式就是元素守恒的：
```plain
JQY2+J2=J3QY2
```
而这个化学方程式就是不合法的，因为它不满足元素守恒：
```plain
JQY2+J2=JQY
```
作为一名资深炼金术士，Yazid 自然是整日沉迷在化学狂暴中。某一天，Yazid 写下了 $n$ 个化学方程式，并把它们放在一边，为后续的研究做着准备。
然而，见习炼金术士 YJQQQAQ 不慎打翻了一瓶绿色的试剂，导致 Yazid 写下的所有化学方程式中，都有**恰好** $1$ 个物质被绿色液体弄得模糊不清了。
暴怒的 Yazid 狠狠地把 YJQQQAQ 批判了一番，并要求他将所有模糊不清的物质重新写出来。除此之外，作为惩罚，**无论原来 Yazid 如何书写这些物质，YJQQQAQ 都必须将它们以“最简式”的形式写出**。
如果不能完成这些任务，Yazid 就会把他从钦钦草原放逐。面对这么多的化学方程式，弱小、无助的 YJQQQAQ 手足无措，于是他找到了钦钦草原最擅长编程的你，请你帮他完成任务。
输入格式
从标准输入读入数据。
第一行 $2$ 个整数 $n,m$，分别表示化学方程式的数目和 Yazid 的书写习惯。其中，书写习惯 $m$ 是 $0$ 到 $3$ 之间的整数，对于不同的 $m$，Yazid 书写物质的方式不同（这一信息可能对你解决部分测试点有帮助）：
* 如果 $m=0$，则 Yazid 在书写方程式时一定**会**将所有物质化为“最简式”；
* 如果 $m=1$，则 Yazid 在书写方程式时一定**会**将所有物质的“虚无元素”省略，且**不会**存在“单一元素”的下标被省略；
* 如果 $m=2$，则 Yazid 在书写方程式时一定**会**将所有物质“单一元素”的下标省略，且**不会**存在“虚无元素”被省略；
* 如果 $m=3$，则 Yazid 在书写方程式时一定**不会**省略“单一元素”的下标，也一定**不会**省略“虚无元素”。
接下来 $n$ 行，每行一个字符串，描述一个被污染的化学方程式。其中，被污染的物质用
数据保证化学方程式严格按照「题目背景」和「题目描述」中的格式，且不存在多余的空格或其他字符。
第一行 $2$ 个整数 $n,m$，分别表示化学方程式的数目和 Yazid 的书写习惯。其中，书写习惯 $m$ 是 $0$ 到 $3$ 之间的整数，对于不同的 $m$，Yazid 书写物质的方式不同（这一信息可能对你解决部分测试点有帮助）：
* 如果 $m=0$，则 Yazid 在书写方程式时一定**会**将所有物质化为“最简式”；
* 如果 $m=1$，则 Yazid 在书写方程式时一定**会**将所有物质的“虚无元素”省略，且**不会**存在“单一元素”的下标被省略；
* 如果 $m=2$，则 Yazid 在书写方程式时一定**会**将所有物质“单一元素”的下标省略，且**不会**存在“虚无元素”被省略；
* 如果 $m=3$，则 Yazid 在书写方程式时一定**不会**省略“单一元素”的下标，也一定**不会**省略“虚无元素”。
接下来 $n$ 行，每行一个字符串，描述一个被污染的化学方程式。其中，被污染的物质用
? 表示，保证对于每一个方程式都会存在恰好 $1$ 个 ?。数据保证化学方程式严格按照「题目背景」和「题目描述」中的格式，且不存在多余的空格或其他字符。
输出格式
输出到标准输出。
输出 $n$ 行，每行一个字符串，表示化为“最简式”的
输出 $n$ 行，每行一个字符串，表示化为“最简式”的
? 所表示的物质。特别地，对于无解的情况（即 ? 表示的物质超出钦钦草原世界化学学科的研究范围），请输出“No Solution”（不含引号）。输入输出样例
输入 #1
3 0 A=? ?=A+B C+O2=?
输出 #1
A AB CO2
输入 #2
3 1 A1=? A1+?=B1 C1+O2=?
输出 #2
A No Solution CO2
输入 #3
1 2 A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0=?
输出 #3
JQY2
输入 #4
2 3 ?=A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0 A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0+A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0=?
输出 #4
JQY2 J2Q2Y4
说明/提示
| 测试点编号 | $m$ | ? 在方程式的最左端 | 等号左边不含 + | 等号右边不含 + |
|-|-|-|-|-|
| 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$ | Yes | | |
| 14 | $1$ | Yes | | |
| 15 | $2$ | Yes | | |
| 16 | $3$ | Yes | | |
| 17 | $0$ | | | |
| 18 | $1$ | | | |
| 19 | $2$ | | | |
| 20 | $3$ | | | |
如表格中“? 在方程式的最左端”为“Yes”，则表示该测试点保证每个字符串的第一个字符均为 `?`；否则无特殊保证。
如表格中“等号左边**不**含 +”为“Yes”，则表示该测试点保证等号左边没有加号（`+`），即等号左边只有一种物质；否则无特殊保证。
如表格中“等号右边**不**含 +”为“Yes”，则表示该测试点保证等号右边没有加号（`+`），即等号右边只有一种物质；否则无特殊保证。
对于所有的测试点，保证 $n\leq 100$，保证每个方程式中等式两边的加号 `+` 都不超过 $5$ 个，这也意味着每行字符串（每个化学方程式）的长度不超过 $635$。
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/王聿中 命题/王聿中 验题/陈宇 Git Repo：https://git.thusaac.org/publish/CodePlus201712 感谢腾讯公司对此次比赛的支持。
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/王聿中 命题/王聿中 验题/陈宇 Git Repo：https://git.thusaac.org/publish/CodePlus201712 感谢腾讯公司对此次比赛的支持。