Isles in a Triangular Grid

A triangular grid is the tiling of the plane by equilateral triangles with side length $1$. A path in the grid is any finite sequence of unit triangles in which every two consecutive triangles share a whole side.

A figure formed by the points of finitely many unit triangles is called an isle if any two grid triangles contained in the figure are joined by some path whose triangles all lie inside the figure.

The shapes in Figures 1.1, 1.2 and 1.3 are isles; the shape in Figure 1.4 is not. The shapes in Figures 2.2, 2.3 and 2.5 are congruent.

For every $n \le 10$ we want a systematic description of all pairwise non-congruent isles that can be built from $n$ unit triangles, together with a count of how many there are.

The boundary of an isle built from at most ten triangles is a closed polygonal line made of unit grid segments. It can be traced without lifting the pencil, following each segment exactly once and returning to the start; a vertex may have to be passed more than once (see Figure 2.4). For isles of at most ten triangles the boundary is always connected and can be traced this way (unlike the shape in Figure 1.2).

Walking around the boundary, after each unit segment you make one of these turns:

• a: turn left by $120^\circ$
• b: turn left by $60^\circ$
• c: go straight ($0^\circ$)
• d: turn right by $60^\circ$
• e: turn right by $120^\circ$

Each closed walk around an isle is described by a word over $\{a, b, c, d, e\}$: the $i$-th letter is the turn made after the $i$-th unit segment. The word has as many letters as the boundary has segments, so it also records the turn after the last segment, even though that turn is not needed to recover the shape. This extra letter helps when rewriting one boundary description as another that differs only in its starting point.

The words cdddcddd, dcdddcdd, cbbbcbbb describe different traversals of the shape in Figure 2.1. The words cbeddcde, adcabcbb, abcbbadc describe different traversals of the shape in Figure 2.2. The words acdabbcb, cddebced describe different traversals of the shape in Figure 2.3.

A closed walk is clockwise if the interior of the shape stays on the right-hand side throughout the walk.

The code of an isle is the word that (1) describes a clockwise walk around the boundary of some isle congruent to the given one, and (2) is the lexicographically smallest among all words satisfying (1).

For the congruent isles in Figures 2.2 and 2.3, listing every clockwise walk gives

beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde

and

bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd,

so their common code is bcedcdde, the smallest of all these words. The code of the isle in Figure 2.4 is aadecddcddde.

Write a program that answers queries of two kinds:

• given the code of an isle of size $k$, output the codes of all isles of size $k + 1$ obtainable by adding one triangle to some isle congruent to it;
• given an integer $n$, output the codes of all isles of size $n$.

The first line contains an integer $t$ ($1 \le t \le 5$), the number of queries. Each of the next $t$ lines holds one query:

• a type 1 query is the letter K, a single space, and the code of an isle formed by at most ten triangles;
• a type 2 query is the letter N, a single space, and an integer $n$ ($1 \le n \le 10$).

Answer the queries in the order given.

• For a type 1 query, print the number of distinct codes of isles obtainable by adding one triangle to isles congruent to the given one, then, on the next line, all those codes in lexicographic order separated by single spaces.
• For a type 2 query, print the number of distinct codes of isles formed by $n$ triangles, then, on the next line, all those codes in lexicographic order separated by single spaces.