Найщасливіший суфікс
Limits: 2 sec., 256 MiB
У Марічки є рядок із \(n\) щасливих цифр 4 та 7.
Зенику дозволено змінити не більше як \(\lfloor \frac{n}{2} \rfloor\) цифр рядка на протилежні (із 4 в 7, або із 7 у 4) так, щоб рядок \(s\) був лексикографічно меншим за усі свої суфікси. Допоможіть Зенику знайти такий змінений рядок, або ж повідомте, що це неможливо.
Input
У єдиному рядку задано рядок \(s\), що складається лише із щасливих цифр 4 та 7.
Output
Якщо досягнути цілі неможливо, виведіть -1. У протилежному разі виведіть шуканий рядок. Якщо існує декілька правильних розв’язків, дозволено вивести будь-який із них.
Constraints
\(1 \le |s| \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
74744 | 44747 |
Input (stdin) | Output (stdout) |
---|---|
74 | -1 |
Notes
Рядок \(s\) вважається
лексикографічно меншим за рядок \(t\),
якщо \(s\) є префіксом \(t\), або ж \(s\) містить меншу цифру у першій позиції, в
якій \(s\) і \(t\) відрізняються. Наприклад,
47
є меншим за 7
, 74
,
477
та 474
, проте більшим за 4
та
44
.
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|