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

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) сopy	Output (stdout) сopy
74744	44747

Input (stdin) сopy	Output (stdout) сopy
74	-1

Notes

Рядок $s$ вважається лексикографічно меншим за рядок $t$, якщо $s$ є префіксом $t$, або ж $s$ містить меншу цифру у першій позиції, в якій $s$ і $t$ відрізняються. Наприклад, 47 є меншим за 7, 74, 477 та 474, проте більшим за 4 та 44.