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
| Wejście | Wyjście | |
|
|