Bus tickets are numbered. All ticket numbers are always written using the same number of digits, with the number of digits used being even. If necessary, the numbers are padded with leading zeros. For example, if 4 digits are used for recording, then 514 will be written as 0514. Tickets are printed on tapes, tickets on each tape are numbered consecutively from 00...01 to 99...99.
A ticket is considered lucky if the sum of the digits of the first half is equal to the sum of the digits of the second half, for example, tickets 1001 and 123051 are lucky, and 7778 and 39 – No. Today Dima got on the bus, and the conductor gave him a ticket with the number N. Since Dima had to travel long enough, but he had to do something, he began to think what number the next lucky ticket would have, issued from the same tape as Dima's ticket . If there are no lucky tickets left in the current feed, Dima is interested in the number of the minimum lucky ticket from the new feed.
The first and only line of the input file contains Dima's ticket number N, written with leading zeros. The number of digits in the number N does not exceed 100,000 and is even.
The program should output the number of the next lucky ticket from the current tape in the same format. If such a ticket does not exist, print the number of the minimum lucky ticket from the new tape. The output should not contain spaces, empty lines at the beginning of the output.
|
Enter |
Output |
Note |
|
0514 |
0523 |
Dima was given a lucky ticket (the sum of the digits of both halves is 5), but Dima is not interested in the number of his ticket, he is interested in the number of the next lucky ticket. |