Polygon Modification with Equilateral Triangle Expansion

You are given a closed polygon defined by a cyclic sequence of unit vectors that form a non‐degenerate polygon, defined by a string S of length n. Each character of S is from the set {a, b, c, d, e, #} and encodes the turning angle between consecutive unit vectors as follows:

Character	Meaning
a	\(\langle L_i,L_{i+1}\rangle=\frac{2\pi}{3}\)
b	\(\langle L_i,L_{i+1}\rangle=\frac{\pi}{3}\)
c	\(\langle L_i,L_{i+1}\rangle=0\)
d	\(\langle L_i,L_{i+1}\rangle=-\frac{\pi}{3}\)
e	\(\langle L_i,L_{i+1}\rangle=-\frac{2\pi}{3}\)
#	\(\vert\langle L_i,L_{i+1}\rangle\vert=\pi\)

Some facts are guaranteed about the original sequence:

• All vectors have length 1.
• The sum \(L_1+L_2+\cdots+L_n=0\) (so the polygon is closed).
• For any pair \(L_i, L_j\), the angle \(\langle L_i,L_j\rangle\) is always an integer multiple of \(\frac{\pi}{3}\) (i.e. multiples of 60°).
• No proper contiguous segment (other than the entire sequence) has a zero vector sum.

We identify the vectors by their direction. Assume the directions are among the six possible ones corresponding to multiples of \(60^\circ\): represent them as integers mod 6 (with 0 corresponding to angle 0, 1 to \(\pi/3\), 2 to \(2\pi/3\), 3 to \(\pi\), etc.). We fix \(L_1\) to have direction 0. Then, given S if the \(i\)th character corresponds to a turning angle \(\delta\) (with the mapping below), we have:

[ L_{i+1} = L_i + \delta \quad(\bmod\ 6) ]

Mapping from characters to \(\delta\) (in mod 6) is:

• a: 2
• b: 1
• c: 0
• d: -1 (i.e. 5 mod 6)
• e: -2 (i.e. 4 mod 6)
• #: 3

---

The modification operation is defined as follows. You choose an index \(1 \le k \le n\) (indices are cyclic, meaning that \(L_0\) is \(L_n\) and \(L_{n+1}\) is \(L_1\)). Then:

1. Construct two unit vectors \(X\) and \(Y\) satisfying \[ \langle L_k, X\rangle = \frac{\pi}{3}, \quad \langle L_k, Y\rangle = -\frac{\pi}{3}. \] In our mod6 representation this means if \(L_k\) has direction \(r\), then \(X\) has direction \((r+1) \bmod 6\) and \(Y\) has direction \((r-1) \bmod 6\).
2. Replace the vector \(L_k\) with the two vectors \(X\) and \(Y\) (in that order) in the sequence.
3. Then, if \(L_{k-1} + X = 0\) (i.e. \(L_{k-1}\) is the opposite of \(X\); in mod6, this means \(L_{k-1} = (X+3) \bmod 6\)), delete both \(L_{k-1}\) and \(X\); similarly, if \(L_{k+1} + Y = 0\) (i.e. \(L_{k+1} = (Y+3) \bmod 6\)), delete both \(L_{k+1}\) and \(Y\). (Indices are taken cyclically.)
4. If after these operations the modified sequence has any proper contiguous subsequence whose vector sum is \(0\) (when considering the sequence cyclically) then the modification is illegal.
5. Otherwise, define the modification result to be the standard representation of the modified sequence. The standard representation is computed by taking all cyclic shifts of the string representation (see below) of the modified sequence and choosing the lexicographically smallest one.
6. Two modification schemes are considered equivalent if the polygons (when the edges are concatenated in order) are congruent. In other words, if their standard representations are identical then they are equivalent.

The string representation for any vector sequence is obtained by converting the angles between consecutive edges to characters. For a sequence of directions \(r_0, r_1, \ldots, r_{m-1}\) (with cyclic wrap‐around), for each edge the turning angle is:

[ \delta_i = (r_{i+1} - r_i) \bmod 6. ]

Then, using the inverse mapping (noting that a difference of 5 corresponds to -1 and 4 corresponds to -2) the mapping is:

• 2 → a
• 1 → b
• 0 → c
• 5 → d
• 4 → e
• 3 → #

---

Your task is: Given the string S (which may not be the standard representation of the polygon) corresponding to the original vector sequence, find all non-equivalent legal modifications. Output the number of distinct legal modification results, and then output each modification result (i.e. the standard representation of the modified sequence) in lexicographical order.

---

Input Format:

A single line containing a nonempty string S composed of characters from {a, b, c, d, e, #}.

Output Format:

On the first line print an integer representing the number of distinct legal modifications.
Then, print each legal modification result (the standard representation string), one per line, in lexicographical order.

Note: It is guaranteed that S represents a valid closed polygon satisfying that no proper contiguous segment has a zero sum vector.

---

Remark on Implementation: You can represent unit vectors by their direction in mod 6. Assume initial direction 0 for \(L_1\). For character to turn mapping, use:

• a: +2
• b: +1
• c: 0
• d: -1 (or 5 mod 6)
• e: -2 (or 4 mod 6)
• #: 3

When checking if a contiguous segment sums to the zero vector (illegal modification), simulate the vector additions in the plane. For accuracy use the fact that the 6 possible directions are at multiples of \(60^\circ\), e.g. represent them using cosine and sine (with a tolerance for floating point comparisons).

inputFormat

A single line containing the string S.

outputFormat

On the first line, output an integer n — the number of distinct legal modifications. Then output n lines, each containing a modification result (the standard representation of the modified vector sequence) in lexicographical order.

sample

bcd

1
bcd

</p>