Absent Substrings in Valid Segmentations

Given a string \(S\) consisting only of lowercase letters, you are allowed to split it into any number of contiguous substrings. However, each substring must have a length of at most \(5\), and any two adjacent substrings must not share any common letter. In other words, if \(s_1, s_2, \ldots, s_k\) is a segmentation of \(S\) (i.e. \(S = s_1 s_2 \cdots s_k\)) then for every \(1 \le i < k\) we require \(s_i \cap s_{i+1} = \emptyset\) (here, \(s_i\) denotes the set of characters in that substring).

Let \(U\) be the set of all distinct substrings of \(S\) of length at most \(5\). A substring \(x \in U\) is called absent if no matter how you split \(S\) into substrings under these restrictions, \(x\) never appears as one of the substrings. Your task is to output all such absent substrings in lexicographical order.

For example, consider \(S=\mathtt{abcdae}\). Note that splitting as \(\mathtt{abcd}\) and \(\mathtt{ae}\) is invalid since both segments contain \(a\), while splitting as \(\mathtt{abcda}\) and \(\mathtt{e}\) is valid.

Input constraints:

• \(S\) only contains lowercase letters.
• The length of each segment in a valid segmentation is at most \(5\).

Note on notation: For any substring \(x\), let \(mask(x)\) be the bitmask corresponding to the set of letters in \(x\) (with \(a\) corresponding to the least–significant bit). Two substrings \(x\) and \(y\) are disjoint if \(mask(x) \wedge mask(y)=0\).

inputFormat

The input consists of a single line containing the string \(S\).

outputFormat

Output the absent substrings (i.e. those that never occur as a segment in any valid segmentation) in lexicographical order, one per line. If there is no such substring, output nothing.

sample

abcdae

abd
ac
ace
ad
ace