Ваше завдання полягає в тому, щоб змінити порядок символів у рядку так, щоб жодні два сусідніх символи не були однаковими.

Який лексикографічно мінімальний такий рядок?

Обмеження

• ~1 \le n \le 10^6~

Формат вхідних даних

Єдиний рядок містить рядок довжиною ~n~ із символів A–Z.

Формат вихідних даних

Надрукуйте лексикографічно мінімальний перевпорядкований рядок, де немає двох однакових суміжних символів. Якщо неможливо створити такий рядок, виведіть -1.

Приклад вхідних даних

HATTIVATTI

Приклад вихідних даних

AHATITITVT