eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Марися і Степан

Марися і Степан

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

Марися і Степан граються в рутенську диво-гру. Правила гри дуже прості: гравці називають по одному числу, той хто назве більше число – виграє. Марися завжди програє, адже, нічого не підозрюючи, називає своє число першою. Степан занадто марновірний, а тому вважає, що якщо число, яке він назве, не буде щасливим, то прийде лихо, і Марися здогадається, в чому причина її програшів. Степан вважає число щасливим, якщо сума цифр першої половини числа рівна сумі цифр другої половини числа (не зважаючи на середню цифру, якщо число складається с непарної кількості цифр). Наприклад, числа 4, 515, 63190 є щасливими, а 10, 112, 1231 – ні.

На наступний день вони домовились зіграти на диво-банан. На превеликий жаль для Степана на початку гри Марися запропонувала йому ходити першим. Тепер Степан розуміє, що лише чудо дозволить йому виграти диво-банан, а тому він вирішив назвати не просто щасливе число, а двічі щасливе. Він вважає, що число двічі щасливе, якщо воно щасливе в звичайному сенсі, а також, якщо сума його цифр на парних та непарних місцях співпадає (окрім, знову ж таки, середньої цифри, якщо число складається з непарної кількості цифр). Наприклад числа 11, 19319 – двічі щасливі, а 3, 414 – ні. На розчарування Степана, Марися швидко придумала число більше за його число і виграла диво-банан.

Внаслідок чи то занадто великої щасливості числа, названого Степаном, чи то азарту самої Марисі, чи то якихось інших невідомих нам обставин на наступний день Марися запропонувала зіграти одразу на два диво-банани, а також, що є найбільш важливим для Степана, Марися захотіла називати число першою. Тепер Степан не хоче змарнувати свого шансу, а тому вам, доведеться написати програму, що за числом, загаданим Марисею, знайде найменше число, що перевищує його і є двічі щасливим, що гарантує перемогу Степана.

Входные данные

У єдиному рядку міститься єдине ціле число – N(1 ≤ N ≤ 10^100000) – число назване Марисею.

Выходные данные

Виведіть найменше число, яке може назвати Степан.

Пример

Входные данные #1
10
Выходные данные #1
11
Источник ACM-ICPC Ukraine 2014, Перший етап, 26 квітня 2014 року