Polyiamond Isle Codes

The problem of polyiamonds deals with creating shapes (called isles) by gluing together equilateral triangles (of side length 1) along their edges. A given isle can be uniquely described by a code that is obtained by traversing its perimeter in a clockwise fashion and noting the type of turn made after each unit segment. The allowed turns (taken immediately after a unit segment) are:

• a: 120° left turn,
• b: 60° left turn,
• c: 0° turn,
• d: 60° right turn,
• e: 120° right turn.

For a given isle, one considers all its clockwise cycles (a clockwise cycle is one in which the interior of the isle remains to the right of the traverse) and determines a code – the lexicographically smallest word among all such cycles. For instance, if the clockwise cycles of two congruent isles are given by:

  beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde
  bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd

their common code is bcedcdde (the lexicographically smallest among all words). Similarly, the code of the isle in another figure is aadecddcddde.

Your task is to write a programme that supports two types of queries:

1. For a given code of an isle of size k, generate the codes of all isles of size k+1 that can be obtained by adding one triangle to it.
2. For a given integer n (with n ≤ 10), generate the codes of all non‐congruent isles of size n (i.e. isles formed by n triangles).

The output should list all valid isle codes (each code being the canonical representation of the corresponding isle) in lexicographical order, one per line.

Note: In this problem the geometric interpretation involves dealing with a polygonal chain whose segments lie along a grid. The turns (given in LaTeX in the allowed set) are: \(a: 120^\circ\ \text{left}\), \(b: 60^\circ\ \text{left}\), \(c: 0^\circ\ \text{(no turn)}\), \(d: 60^\circ\ \text{right}\), \(e: 120^\circ\ \text{right}\). The correct generation of new isles by adding a triangle is nontrivial, but the code of an isle is uniquely defined as the lexicographically smallest among all clockwise cycle descriptions.

inputFormat

The input consists of a single line. It can be in one of the following two forms:

• If the line represents an integer n (with 1 ≤ n ≤ 10), then it denotes that you are to generate the codes of all non‐congruent isles formed by n triangles.
• If the line is a string composed only of the letters {a,b,c,d,e}, it is the code of an isle of size k. In that case, you must generate the codes of all isles of size k+1 obtainable by adding one triangle to the given isle.

The input is guaranteed to be valid.

outputFormat

Output all the valid isle codes in lexicographical order, one per line.

sample

1

NotImplemented