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

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