Hide

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

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

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.9medium
Statistics Show