Mirko and Slavko's Lexicographical Game

Mirko and Slavko are playing a game with a sequence of letters. Initially, they write down a sequence \(S\) containing \(n\) letters. They take turns to remove one letter from \(S\) and append it to the end of their own word. Mirko starts the game and always removes the rightmost letter from \(S\). On his turn, Slavko may remove any letter from the remaining sequence.

The game ends when the sequence \(S\) is empty. Let \(M\) be the word constructed by Mirko and \(W\) be the word constructed by Slavko. A word \(X\) is considered more beautiful than a word \(Y\) if \(X\) is lexicographically smaller than \(Y\) (i.e. when compared in dictionary order, \(X\) comes before \(Y\)). At the end of the game, Slavko wins if and only if \(W M\), then Slavko loses.

Knowing that Mirko always picks the rightmost letter, Slavko wonders whether he can win and, if possible, what is the lexicographically smallest winning word he can construct. In other words, given the initial sequence \(S\), determine if there exists a strategy for Slavko such that his final word \(W\) satisfies \(W < M\) where \(M\) is Mirko's final word. If such a strategy exists, output the lexicographically smallest possible \(W\) among all winning strategies; otherwise, output NO.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The input consists of a single line containing the string \(S\) (the sequence of letters). The length of the string is \(n\).

outputFormat

If Slavko can win (i.e. there is a strategy that produces a word \(W\) where \(W < M\)), output the lexicographically smallest winning word \(W\). Otherwise, output NO.

sample

ab

a