Practice Numbers with the exercise "Next growing number"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Numbers

Statement

Goal

A growing number is a number where each digit, from left to right, is greater than or equal to the previous one.

Given a number n, which may or may not be a growing number, you have to find the first growing number > n.

Example:
With n = 19, the first growing number greater than n is 22, because both 20 and 21 have a second digit that is smaller than the first one.

Note: This problem can be solved without converting n to a number.

Input

line 1: a string representing the number n

Output

line 1: the first growing number > n

Constraints

n < 10^19

Example

Input

Output

Solve it

A higher resolution is required to access the IDE