Найщасливіший суфікс
Обмеження: 2 сек., 256 МіБ
У Марічки є рядок із \(n\) щасливих цифр 4 та 7.
Зенику дозволено змінити не більше як \(\lfloor \frac{n}{2} \rfloor\) цифр рядка на протилежні (із 4 в 7, або із 7 у 4) так, щоб рядок \(s\) був лексикографічно меншим за усі свої суфікси. Допоможіть Зенику знайти такий змінений рядок, або ж повідомте, що це неможливо.
Вхідні дані
У єдиному рядку задано рядок \(s\), що складається лише із щасливих цифр 4 та 7.
Вихідні дані
Якщо досягнути цілі неможливо, виведіть -1. У протилежному разі виведіть шуканий рядок. Якщо існує декілька правильних розв’язків, дозволено вивести будь-який із них.
Обмеження
\(1 \le |s| \le 10^5\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
74744 | 44747 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
74 | -1 |
Примітки
Рядок \(s\) вважається
лексикографічно меншим за рядок \(t\),
якщо \(s\) є префіксом \(t\), або ж \(s\) містить меншу цифру у першій позиції, в
якій \(s\) і \(t\) відрізняються. Наприклад,
47
є меншим за 7
, 74
,
477
та 474
, проте більшим за 4
та
44
.
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|