Problem D
Groupthink

Image by kabliczech (iStock), Used under license

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.

Input

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.

Output

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”.

2
0 0 0
0 1 1
1 0 1
1 1 0

group

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