Маріся и Степан
Марися и Степан играют в рутенскую чудо-игру. Правила игры просты: каждый игрок называет число, и тот, кто назовет большее, побеждает. Марися всегда проигрывает, так как она называет свое число первой. Степан, будучи суеверным, считает, что если его число не будет счастливым, то его постигнет неудача, и Марися поймет, почему она проигрывает. Степан считает число счастливым, если сумма цифр первой половины числа равна сумме цифр второй половины (исключая среднюю цифру, если число состоит из нечетного количества цифр). Например, числа 4, 515, 63190 — счастливые, а 10, 112, 1231 — нет.
На следующий день они решили сыграть на чудо-банан. К сожалению для Степана, Марися предложила ему ходить первым. Теперь Степан понимает, что только чудо поможет ему выиграть чудо-банан, и поэтому он решил назвать не просто счастливое число, а дважды счастливое. Он считает число дважды счастливым, если оно счастливое в обычном смысле, а также если сумма его цифр на четных и нечетных позициях совпадает (опять же, исключая среднюю цифру, если число состоит из нечетного количества цифр). Например, числа 11, 19319 — дважды счастливые, а 3, 414 — нет. К разочарованию Степана, Марися быстро придумала число больше его и выиграла чудо-банан.
Возможно, из-за слишком большой счастливости числа, названного Степаном, или из-за азарта Мариси, или по каким-то другим неизвестным причинам, на следующий день Марися предложила сыграть сразу на два чудо-банана, и, что наиболее важно для Степана, она захотела называть число первой. Теперь Степан не хочет упустить свой шанс, и вам нужно написать программу, которая по числу, названному Марисей, найдет наименьшее число, которое больше его и является дважды счастливым, чтобы Степан мог победить.
Входные данные
В единственной строке содержится одно целое число — N (1 ≤ N ≤ 10^100000) — число, названное Марисей.
Выходные данные
Выведите наименьшее число, которое может назвать Степан.