24. Счастливый номер

В ящике вашего офисного стола лежит печать, которая при штампе ставит число из $n$ цифр (где $n$ — чётное число). После штампа число на печати увеличивается на $1$. Если больше увеличивать число нельзя (если оно станет состоять из $n + 1$ цифры), все цифры на печати автоматически ставятся в ноль. Также число на печати в любой момент может содержать ведущие нули.

Счастливым номером вы считаете такой, у которого сумма первых $\frac{n}{2}$ цифр совпадает с суммой вторых $\frac{n}{2}$ цифр и эта сумма больше нуля. Например, при $n = 4$ число $1234$ не является счастливым, а $1423$ является.

Вы видите, что на печати сейчас выставлено число $x$ (не обязательно счастливое). Найдите следующее счастливое число, которое окажется на печати.

На вход программе выдаётся число $x$ ($0 \le x \le 10^{100\,000}$), состоящее из чётного числа цифр — числа на печати. В записи числа $x$ могут присутствовать ведущие нули.

Выведите одно число — следующий счастливый номер в таком же формате. Если такого не существует, выведите минимальный счастливый номер. В выводе не должно быть пробелов и пустых строк в начале.

В первом тесте на печати выставлено число $1422$, не являющееся счастливым, так как $1 + 4 \neq 2 + 2$. Следующее за ним, $1423$, является счастливым, так как $1 + 4 = 2 + 3$.