Problem description

Michał ma napis składający się z małych liter alfabetu angielskiego. Trochę mu się ten napis nie podoba, bo może potencjalnie zawierać takie same litery obok siebie. Czy możesz przestawić litery w jego napisie, aby nie zawierał dwóch takich samych liter obok siebie? Michał zadowoli się jednak jedynie najmniejszym leksykograficznie napisem. Porównując leksykograficznie dwa napisy, mniejszy jest ten, w którym na pierwszej różniącującej pozycji jest wcześniejszy znak w alfabecie.

Napisz program, który wczyta napis Michała, wyznaczy najmniejszy leksykograficznie dobry napis, w którym nie ma dwóch takich samych liter i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego – napis Michała.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać ciąg tych samych małych liter alfabetu angielskiego co z wejścia – najmniejsze leksykograficznie ustawienie tych liter, aby żadne dwa znaki obok siebie nie były takie same.

Jeżeli rozwiązanie nie istnieje, zamiast tego należy wypisać tylko jedno słowo NIE.

Ograniczenia

Długość napisu z wejścia nie przekracza 500 000 znaków.

Przykład

aacaabbcz

ababacacz