DB's crush loves good number. The number contains digits 1 and 2 in their decimal representation is known as a good number. DB wants to impress his crush in the upcoming new year. So he wants to give a magical number instead of a good number as a gift. A good number is magical if it's decimal representation contains an equal amount of digits 1 and 2. For example, numbers 12, 2211 are super magical and 1, 122 are not. DB has a positive integer n but he doesn't know how to generate a magical number. Help him to find the least magical number which is greater than or equal to n.

Input:

The only line contains a positive integer n (1 ≤ n ≤ 10^100000). This number doesn't have leading zeroes.

Output:

Output the least magical number that is greater than or equal to n.