Description

所谓化学方程式，即是用加号（+）和等号（=）连接一些化学物质的式子。保证一个化学方程式中含有恰好一个等号（=）。化学物质由一些元素（用大写字母A至Z表示）加上下标（保证下标为不超过 $9$ 的非负整数）连接而成的。例如：JQY2、A0J1QY2 等。书写时需要保证字典序越小的字母排在越前面。

需要注意的是，像 A0J1QY2 这样的物质书写同样是合法的，虽然事实上它和 JQY2 是等价的。我们把下标为 $1$ 的元素称为“单一元素”，把下标为 $0$ 的元素称为“虚无元素”。在书写一种物质时，我们既可以省去“单一元素”的下标，又可以直接省去“虚无元素”。特别地，我们把用这两种规则省略至最简的书写称为该物质的“最简式”。例如，JQY2 就是 A0J1Q1Y2 的最简式。

既然称之为“方程式”，元素守恒就是必须的了。对于一个化学方程式，元素守恒指的是指等号两边所有元素的下标之和相等。比如，这个化学方程式就是元素守恒的：

JQY2+J2=J3QY2

而这个化学方程式就是不合法的，因为它不满足元素守恒：

JQY2+J2=JQY

作为一名资深炼金术士，Yazid 自然是整日沉迷在化学狂暴中。某一天，Yazid 写下了 $n$ 个化学方程式，并把它们放在一边，为后续的研究做着准备。

然而，见习炼金术士 YJQQQAQ 不慎打翻了一瓶绿色的试剂，导致 Yazid 写下的所有化学方程式中，都有恰好 $1$ 个物质被绿色液体弄得模糊不清了。

暴怒的 Yazid 狠狠地把 YJQQQAQ 批判了一番，并要求他将所有模糊不清的物质重新写出来。除此之外，作为惩罚，无论原来 Yazid 如何书写这些物质，YJQQQAQ 都必须将它们以“最简式”的形式写出。

如果不能完成这些任务，Yazid 就会把他从钦钦草原放逐。面对这么多的化学方程式，弱小、无助的 YJQQQAQ 手足无措，于是他找到了钦钦草原最擅长编程的你，请你帮他完成任务。

Input Format

从标准输入读入数据。

第一行 $2$ 个整数 $n,m$，分别表示化学方程式的数目和Yazid的书写习惯。其中，书写习惯 $m$ 是 $0$ 到 $3$ 之间的整数，对于不同的 $m$，Yazid 书写物质的方式不同（这一信息可能对你解决部分测试点有帮助）：

如果 $m=0$，则 Yazid 在书写方程式时一定会将所有物质化为“最简式”；

如果 $m=1$，则 Yazid 在书写方程式时一定会将所有物质的“虚无元素”省略，且不会存在“单一元素”的下标被省略；

如果 $m=2$，则 Yazid 在书写方程式时一定会将所有物质“单一元素”的下标省略，且不会存在“虚无元素”被省略；

如果 $m=3$，则 Yazid 在书写方程式时一定不会省略“单一元素”的下标，也一定不会省略“虚无元素”。

接下来 $n$ 行，每行一个字符串，描述一个被污染的化学方程式。其中，被污染的物质用?表示，保证对于每一个方程式都会存在恰好 $1$ 个?。

数据保证化学方程式严格按照题目背景和题目描述中的格式，且不存在多余的空格或其他字符。

Output Format

输出到标准输出。

输出 $n$ 行，每行一个字符串，表示化为“最简式”的?所表示的物质。特别地，对于无解的情况（即?表示的物质超出钦钦草原世界化学学科的研究范围），请输出 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

如表格中“?在方程式的最左端”为 Yes，则表示该测试点保证每个字符串的第一个字符均为?；否则无特殊保证。

如表格中“等号左边不含+”为 Yes，则表示该测试点保证等号左边没有加号（+），即等号左边只有一种物质；否则无特殊保证。

如表格中“等号右边不含+”为 Yes，则表示该测试点保证等号右边没有加号（+），即等号右边只有一种物质；否则无特殊保证。

对于所有的测试点，保证 $n\leq 100$，保证每个方程式中等式两边的加号+都不超过 $5$ 个，这也意味着每行字符串（每个化学方程式）的长度不超过 $635$。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/陈宇

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

感谢腾讯公司对此次比赛的支持。

感谢