Custom Palindromic Partition

Given a string S, determine whether it is a palindromic string in the "custom" sense defined by Xiaoming. Xiaoming defines a string S as a palindromic string if there exists a segmentation of S into n (with n > 1) non‐empty contiguous substrings:

[ S = S_1 + S_2 + \cdots + S_n,]

such that for each i in [1, n], one of the following holds between the i-th substring S_i and its corresponding substring from the other end S_{n-i+1}:

• S_i = S_{n-i+1}, or
• S_i and S_{n-i+1} are reverses of each other (i.e. \(S_i^R = S_{n-i+1}\)).

If S meets the above criteria, you are to partition S into as many substrings as possible (i.e. maximize n) under these rules. Otherwise, report that S cannot be segmented in this manner.

Notes:

• The operation \(+\) denotes string concatenation.
• For an odd number of segments, the middle segment is paired with itself and thus trivially satisfies the condition.
• At least 2 segments (n > 1) must be obtained for the string to be considered valid.

inputFormat

The input consists of a single line containing string S (with 1 \(\leq |S| \leq 10^5\)).

outputFormat

If there exists a valid segmentation of S as defined above, then output the maximum number of substrings n in the first line, followed by n lines each containing one substring in order. Otherwise, output a single line containing NO (in uppercase).

sample

abba

4
a
b
b
a

</p>