B. Balarila
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Here is a well-known trick question about Tagalog:

How many letters are in the word, "bunga"?

The answer is, of course, four, because in Tagalog, "ng" is considered to be a single "letter" (albeit written with two symbols)—that is, the letters are b-u-ng-a. So, for example, the word "pangngalan" has 8 letters.

Since Tagalog is so good, Alice wants to create a Tagalog 2. In Tagalog 2, she will choose two distinct consonants—let's write them as $$$xy$$$—such that this substring of two characters is counted as a single "letter" (each other character, as normal, counts as one letter). Given a string $$$s$$$, she must choose these consonants $$$x$$$ and $$$y$$$ such that the string $$$s$$$ is counted as having $$$k$$$ letters in Tagalog 2. If there are multiple possible answers, Alice wants the lexicographically smallest one (i.e. the one that would come earliest in the dictionary).

Please help Alice answer this question for all integers $$$k$$$ from $$$1$$$ to $$$|s|$$$ (the length of $$$s$$$). Good luck!

For the sake of this problem, y is always considered as a consonant.

Input

Input consists of a single line containing the string $$$s$$$.

Output

Output $$$|s|$$$ space-separated strings, the $$$k$$$th of which is the answer to the problem for that value of $$$k$$$:

  • If the task is possible, output the two lowercase consonants $$$xy$$$ that answer the question. If the task is not possible, output NO instead.
Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{The string $s$ contains only lowercase letters.} \\ 1 \leq |s| \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & |s| \leq 5 \\ \hline 2 & \mathbf{30} & |s| \leq 500 \\ \hline 3 & \mathbf{30} & |s| \leq 5\times 10^4 \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
bunga
Output
NO NO NO ng bc
Input
thwth
Output
NO NO th hw bc
Note

(Unimportant historical footnote): This quirk was decided on as a carryover from the fact that the velar nasal sound (represented in IPA notation as ŋ) is represented by its own standalone symbol ᜅ in the Baybayin script used in the pre-colonial Philippines, mostly in Luzon. The switch to the "ng" digraph happened during the time of Spanish colonization, when the Philippines adopted the Latin alphabet. And in fact, even then, there are records of Spanish documents representing the ŋ sound with the single symbol g̃ in their writings (think of ñ being used for the "ny-" sound) before the use of "ng" superseded it.