반군

집합 $S$ 위의 이항연산(binary operation)은 $S$의 원소로 이루어진 각 순서쌍에 $S$의 원소 하나를 대응시키는 함수이다. 이항연산은 보통 *, +, # 같은 특별한 기호로 나타낸다. 예를 들어 집합 $S = {a, b, c}$ 위의 어떤 이항연산을 기호 #로 나타내면, a#b는 $S$의 어떤 원소와 같으며 b#a, a#a, a#c 등 가능한 모든 순서쌍도 마찬가지이다.

이 정의에 따르면 모든 정수의 집합에서 정의된 덧셈, 뺄셈, 곱셈은 모두 이항연산이다. 그러나 (정수 나눗셈이 아닌 보통의) 나눗셈은 정수 집합에서 이항연산이 아니다. 1/2 = 0.5는 정수가 아니기 때문이다.

정의에서 "순서"라는 표현이 중요한 이유는, a#b에 대응되는 원소가 b#a에 대응되는 원소와 다를 수 있기 때문이다. 정수의 뺄셈이 그 예로, 5-3은 3-5와 같지 않다. 집합의 모든 원소 $x$, $y$에 대해 x#y = y#x가 성립하면 그 이항연산은 교환법칙이 성립한다(commutative)고 한다. 정수 집합의 표준 덧셈은 교환법칙이 성립한다.

이 문제에서는 원소가 1개에서 26개까지인 작은 집합만 다룬다. 이런 작은 집합에서는 연산을 정의하는 대응 관계를 "곱셈표(multiplication table)" 형태로 모두 나열할 수 있다. 예를 들어 집합 $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가 a#b와 같지 않으므로 교환법칙이 성립하지 않는다.

집합 $S$ 위의 이항연산 #가 모든 원소 $x$, $y$, $z$에 대해 (x#y)#z = x#(y#z)를 만족하면 결합법칙이 성립한다(associative)고 한다. 위 표의 예는 (a#b)#c가 a#(b#c)와 같지 않으므로 결합법칙이 성립하지 않는다. 이항연산 #가 결합법칙을 만족하면 쌍 $\langle S, # \rangle$은 반군(semigroup)을 이룬다고 한다. 연산이 결합법칙과 교환법칙을 모두 만족하면 그 반군을 교환반군(commutative semigroup)이라고 한다.

이항연산을 정의하는 "곱셈표"와 함께 집합의 원소들을 읽어, 그 연산을 가진 집합 $S$가 반군을 이루는지 판정한다. 반군을 이루지 않으면 반군이 아니라고 보고하고 그 이유를 밝힌다. 반군을 이루면 그 반군이 교환반군인지도 확인한다.

따라서 각 집합과 표에 대해 다음 네 가지 결과 중 정확히 하나가 나온다.

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

처음 세 결과에서는 $x$, $y$, $z$ 자리에 정의를 위반하는 반례가 되는 실제 집합 원소를 넣는다. 반례가 여러 개면 표를 위에서 아래로(행 우선), 각 행에서는 왼쪽에서 오른쪽으로 훑을 때 가장 먼저 발견되는 반례를 보고한다. 결합법칙 위반은 $x$, $y$, $z$ 순서로 (집합에 주어진 순서대로) 중첩 반복했을 때 처음 실패하는 삼중항을 보고한다.

첫 줄에는 정수 $n$ ($1 \le n \le 26$)이 주어진다.

다음 줄에는 서로 다른 소문자 $n$개가 주어진다. 이 문자들은 집합의 원소이며 모두 다르지만 반드시 알파벳 순으로 정렬되어 있지는 않다.

그다음 $n$개의 줄에는 위 원소들에 대응하는 곱셈표의 내부가 주어진다. 각 줄에는 소문자 $n$개가 들어 있고, 첫 줄이 표의 첫 번째 행이다. 표의 행과 열의 순서는 집합을 정의한 줄의 원소 순서와 일치한다.

표 다음에는 정수 $n$ ($0 \le n \le 26$)이 주어진다. $n > 0$이면 이어지는 $n+1$개의 줄에 또 다른 집합과 표가 있으며 이것도 처리한다. $n = 0$이면 입력이 끝난 것이다.

입력에서 찾은 각 집합과 표에 대해 다음을 출력한다.

1. 입력과 같은 순서로 $S$의 원소를 다음 형식으로 나열한다: S = {a,b,c,d}
2. 공백 한 칸으로 시작하고 문자 #| 뒤에 집합의 $n$개 원소(공백이나 쉼표 없이)를 붙인 줄. 예(앞에 공백 한 칸): #|abcd
3. 공백 한 칸으로 시작하고 문자 -+ 뒤에 대시 -를 $n$개 붙인 줄. 예(앞에 공백 한 칸): -+----
4. 곱셈표의 $n$개 행을 입력과 같은 순서로 나열한다. $i$번째 줄은 공백 한 칸으로 시작하고, $S$의 $i$번째 원소, |, 표 $i$번째 행의 $n$개 문자(공백 없이) 순으로 이어진다. 예(앞에 공백 한 칸): a|abcd
5. 빈 줄 하나.
6. 판정 결과를 한 줄로 출력한다. 위의 네 가지 중 하나여야 한다.
7. 대시 - 30개로 이루어진 줄.
8. 이 보고서를 다음 보고서와 구분하는 빈 줄 하나.