One of the most fundamental structures in abstract algebra is called a magma. A magma is a pair $(M,\bullet )$, where $M$ is a nonempty set and $\bullet $ is a binary operation on $M$. This means that $\bullet $ maps each ordered pair of elements $(x,y)$ in $M$ to an element in $M$ (in other words, $\bullet $ is a function from $M \times M$ to $M$). The element to which $\bullet $ maps $(x,y)$ is denoted $x \bullet y$.
Magmas that satisfy certain properties are given more specialized names. Here are three important properties that $(M,\bullet )$ could satisfy:
P1 (associativity): For all $x,y,z \in M$, $(x \bullet y) \bullet z = x \bullet (y \bullet z)$.
P2 (identity): There is an element $I \in M$ such that $x \bullet I = I \bullet x = x$ for all $x \in M$ ($I$ is called an identity).
P3 [depends on P2] (inverses): There is an identity $I \in M$, and for every $x \in M$, there exists $x^* \in M$ such that $x \bullet x^* = x^* \bullet x = I$ ($x^*$ is called an inverse of $x$).
A magma that satisfies P1 is called a semigroup. A semigroup that satisfies P2 is called a monoid. A monoid that satisfies P3 is called a group. Given a magma $(M,\bullet )$, determine its most specialized name.
The input consists of a single test case specifying a magma $(M,\bullet )$. The first line contains an integer $n$ $(1 \leq n \leq 120)$, the size of $M$. Assume that the elements of $M$ are indexed $0,1,2,\ldots ,n-1$. Each of the next $n^2$ lines contains three integers $i~ j~ k$ $(0 \leq i,j,k \leq n-1)$, meaning that $x \bullet y = z$, where $x$ is the element indexed by $i$, $y$ is the element indexed by $j$, and $z$ is the element indexed by $k$. Each ordered pair $(i,j)$ will appear exactly once as the first two values on a line.
The output consists of a single line. Output group if $(M,\bullet )$ satisfies P1, P2, and P3. Output monoid if $(M,\bullet )$ satisfies P1 and P2, but not P3. Output semigroup if $(M,\bullet )$ satisfies P1, but not P2 (and therefore not P3). Otherwise, output magma.
Sample Input 1 | Sample Output 1 |
---|---|
2 0 0 0 0 1 1 1 0 1 1 1 0 |
group |
Sample Input 2 | Sample Output 2 |
---|---|
3 1 2 1 2 0 0 0 1 0 2 2 2 1 0 0 0 0 0 2 1 1 0 2 0 1 1 2 |
monoid |