Octagons#2642

Octagons

1 seconde
64 mégaoctets
Très difficile

Below is a picture of an infinite hyperbolic tessellation of octagons. If we think of this as a graph of vertices (of degree three), then there exists an isomorphism of the graph that maps any vertex onto any other vertex . Every edge is given a label from the set \{a, b, c\} in such a way that every vertex has all three types of edges incident to it, and the labels alternate around each octagon. Part of this labeling is illustrated in the diagram.

So, a path in this graph (starting from any vertex) can be specified by a sequence of edge labels. Your task is to write a program which, given a sequence of labels such as , outputs if the path ends at the same vertex where it started, and otherwise.

Entrée

The input will begin with a number Z \leq 200 on a single line. This is followed by lines, each of which is a sequence of length at least and at most of 'a', 'b', and 'c'.

Sortie

For each input case, output or , each on a separate line.

Exemples

Exemple 1

Loading
Loading