Найщасливіший суфікс

Обмеження: 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.