本题没有可用的提交语言。

题目描述

集合 ( S ) 上的二元运算是一个函数，它为 ( S ) 中每个有序元素对分配 ( S ) 中的唯一元素。我们通常使用特殊符号（如 * 或 +）表示二元运算。例如，若用符号 '#' 表示集合 ( S = {a, b, c} ) 上的某个二元运算，则 ( a#b )、( b#a )、( a#a ) 等均对应 ( S ) 中的某个元素。

根据定义，整数集上的加法、减法和乘法均为二元运算，但除法（数学意义上的除法，非整数除法）不是，因为 ( 1 \div 2 = 0.5 ) 不属于整数集。

定义中的“有序”很重要，这意味着 ( a#b ) 可能不等于 ( b#a )。例如整数减法：( 5 - 3 \neq 3 - 5 )。若对所有 ( x, y \in S ) 均有 ( x#y = y#x )，则称该运算为交换的。整数加法是交换的。

本题仅处理小集合（1到26个元素）。对于这类集合，二元运算可通过“乘法表”定义。例如，集合 ( S = {a, b, c} ) 上的运算 '#' 可表示为：

# | a b c  
---------  
a | b c b  
b | a c b  
c | c b a  

表中左列表示有序对的第一个元素，顶行表示第二个元素。例如，( a#b = c )，( b#a = a )，( c#c = a )。注意，运算结果必须属于集合 ( S )，且该运算未必是交换的（如 ( b#a \neq a#b )）。

若对所有 ( x, y, z \in S )，有 ( (x#y)#z = x#(y#z) )，则称运算 '#' 是结合的。此时，( \langle S, # \rangle ) 构成半群。若运算同时是交换的，则称为交换半群。

输入格式

1. 第一行：整数 ( n )（( 1 \leq n \leq 26 )），表示集合元素个数。
2. 第二行：( n ) 个唯一小写字母，按顺序表示集合 ( S ) 的元素。
3. 接下来 ( n ) 行：每行 ( n ) 个小写字母，表示运算表的第 ( i ) 行（对应集合中第 ( i ) 个元素作为第一个操作数）。
4. 后续行：一个整数 ( m )。若 ( m > 0 )，则重复上述 ( m ) 个集合的输入；若 ( m = 0 )，输入结束。

输出格式

对每个集合和运算表，输出以下内容：

1. 集合元素列表：按输入顺序，格式为 S = {a,b,c,d}。
2. 运算表表头：首行以 #| 开头，后跟集合元素（无分隔符），如 #|abcd。
3. 分隔线：以 -+ 开头，后跟 ( n ) 个短横线，如 -+----。
4. 运算表行：每行以集合元素开头，后跟 | 和该行的运算结果，如 a|abcd（无空格）。
5. 空行。
6. 判定结果（四选一）：
   • 若存在运算结果不属于集合，输出：NOT A SEMIGROUP: x#y = z WHICH IS NOT AN ELEMENT OF THE SET，其中 ( x, y, z ) 为字典序最小的反例。
   • 若运算结果均合法但存在结合律反例，输出：NOT A SEMIGROUP: (x#y)#z IS NOT EQUAL TO x#(y#z)，其中 ( x, y, z ) 为字典序最小的反例。
   • 若为半群但非交换，输出：SEMIGROUP BUT NOT COMMUTATIVE (x#y IS NOT EQUAL TO y#x)，其中 ( x, y ) 为字典序最小的反例。
   • 若为交换半群，输出：COMMUTATIVE SEMIGROUP。
7. 30个短横线组成的分隔线。
8. 空行（分隔不同集合的输出）。

输入示例1

3  
abc  
abc  
bca  
cab  
3  
abc  
abc  
bca  
cad  
4  
acdb  
aaaa  
aaca  
aada  
aaab  
5  
abcde  
aaaaa  
bbabb  
cccbc  
ddddd  
eeeee  
0  

输出示例1

S = {a,b,c}  
 #|abc  
 -+---  
 a|abc  
 b|bca  
 c|cab  

COMMUTATIVE SEMIGROUP  
------------------------------  

S = {a,b,c}  
 #|abc  
 -+---  
 a|abc  
 b|bca  
 c|cad  

NOT A SEMIGROUP: c#c = d  WHICH IS NOT AN ELEMENT OF THE SET  
------------------------------  

S = {a,c,d,b}  
 #|acdb  
 -+----  
 a|aaaa  
 c|aaca  
 d|aada  
 b|aaab  

SEMIGROUP BUT NOT COMMUTATIVE  (c#d IS NOT EQUAL TO d#c)  
------------------------------  

S = {a,b,c,d,e}  
 #|abcde  
 -+-----  
 a|aaaaa  
 b|bbabb  
 c|cccbc  
 d|ddddd  
 e|eeeee  

NOT A SEMIGROUP: (b#a)#c IS NOT EQUAL TO b#(a#c)  
------------------------------  

来源

Mid-Central USA 1996