Semigroups

A binary operation on a set $S$ is a function that assigns to each ordered pair of elements of $S$ a unique element of $S$. We usually use a special symbol (such as *, +, or #) to represent a binary operation. For example, if we use the symbol # for some binary operation on the set $S = {a, b, c}$, then a#b equals some element of $S$, and so do b#a, a#a, a#c, and every other possible ordered pair.

From this definition, ordinary addition, subtraction, and multiplication are all binary operations on the set of all integers. However, division (the mathematical kind, not integer division) is not a binary operation on the integers, since 1/2 = 0.5 is not an integer.

The word "ordered" in the definition matters, because it allows the element assigned to a#b to differ from the one assigned to b#a. Integer subtraction is an example, since 5-3 is not equal to 3-5. If x#y = y#x holds for all elements $x$ and $y$ of the set, we say the binary operation is commutative. Ordinary addition on the integers is commutative.

For the rest of this problem we consider only small sets (1 to 26 elements). For such small sets, the assignments that define an operation can be written out fully as a "multiplication table". For instance, the binary operation # on $S = {a, b, c}$ might be defined by:

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

The left column gives the first element of the ordered pair and the top row gives the second. So in this example a#b = c, b#a = a, and c#c = a. The body of the table must consist solely of elements of $S$, which must hold for any binary operation. This operation is not commutative, since b#a is not equal to a#b.

A binary operation # on a set $S$ is associative if (x#y)#z = x#(y#z) for all elements $x$, $y$, and $z$ of the set. In the table above the operation is not associative, since (a#b)#c is not equal to a#(b#c). If a binary operation # is associative, then the pair $\langle S, # \rangle$ forms a semigroup. If the operation is both associative and commutative, the semigroup is a commutative semigroup.

Read the elements of a set together with the "multiplication table" that defines a binary operation, and decide whether the set $S$ with that operation forms a semigroup. If it does not, report that it is not a semigroup and state why. If it does form a semigroup, also check whether the semigroup is commutative.

Thus, for each set and table, exactly one of the following four results applies:

NOT A SEMIGROUP: x#y = z  WHICH IS NOT AN ELEMENT OF THE SET
NOT A SEMIGROUP: (x#y)#z IS NOT EQUAL TO x#(y#z)
SEMIGROUP BUT NOT COMMUTATIVE  (x#y IS NOT EQUAL TO y#x)
COMMUTATIVE SEMIGROUP

In the first three results, substitute the actual elements of the set that form a counter-example to the definition. When more than one counter-example exists, report the first one found by scanning the table top to bottom (row major) and left to right within each row; for an associativity failure, report the first triple found when iterating $x$, then $y$, then $z$ in the set's given order.

The first line contains an integer $n$ ($1 \le n \le 26$).

The next line contains $n$ distinct lowercase letters. These are the elements of the set; they are all different but not necessarily in alphabetical order.

The next $n$ lines contain the body of the multiplication table for those elements. Each line contains $n$ lowercase letters; the first such line is the first row of the table body. The order of the rows and columns matches the order of the elements on the line that defines the set.

After the table, a line contains an integer $n$ ($0 \le n \le 26$). If $n > 0$, another set and table follow in the next $n+1$ lines and must also be processed. If $n = 0$, the input has ended.

For each set and table in the input, output the following:

1. The elements of $S$ in the same order as the input, in this format: S = {a,b,c,d}
2. A line that starts with one space, then the characters #|, then the $n$ elements of the set (no spaces or commas). Example (with a leading space): #|abcd
3. A line that starts with one space, then the characters -+, then $n$ dashes -. Example (with a leading space): -+----
4. The $n$ rows of the multiplication table in the same order as the input. The $i$-th line starts with one space, then the $i$-th element of the set, then |, then the $n$ characters of the $i$-th table row (no spaces). Example (with a leading space): a|abcd
5. One blank line.
6. One line reporting the result, which must be one of the four possibilities above.
7. A line of 30 dashes.
8. One blank line separating this report from the following report.