Marisia and Stepan
Marisia and Stepan are playing a Ruthenian wonder-game with simple rules: each player names a number, and the player who names the larger number wins. Marisia always loses because she names her number first. Stepan, however, is superstitious and believes that if the number he names isn't lucky, misfortune will follow, and Marisia will discover why she keeps losing. A number is considered lucky if the sum of the digits in its first half equals the sum of the digits in its second half (ignoring the middle digit if the number has an odd number of digits). For instance, 4, 515, and 63190 are lucky numbers, while 10, 112, and 1231 are not.
The next day, they decided to play for a wonder-banana. Unfortunately for Stepan, Marisia suggested he go first. Realizing that only a miracle could help him win the wonder-banana, Stepan decided to name a number that is not just lucky, but twice-lucky. A number is twice-lucky if it is lucky in the usual sense and also if the sum of its digits in even positions equals the sum of its digits in odd positions (again, excluding the middle digit if the number has an odd number of digits). For example, 11 and 19319 are twice-lucky, while 3 and 414 are not. Despite his efforts, Marisia quickly named a larger number and won the wonder-banana.
The following day, perhaps due to the excessive luckiness of Stepan's number, Marisia's excitement, or some other unknown reason, Marisia proposed playing for two wonder-bananas at once. Crucially for Stepan, Marisia wanted to name her number first. Determined not to miss his chance, Stepan needs your help to write a program that, given the number named by Marisia, finds the smallest number that is greater than hers and is twice-lucky, ensuring his victory.
Input
The input consists of a single line containing a single integer—N (1 ≤ N ≤ 10^100000)—the number named by Marisia.
Output
Output the smallest number that Stepan can name.