Next Higher Number

Given a number represented as a string of digits, your task is to determine the next higher number that can be formed by rearranging its digits. In other words, find the next permutation in lexicographical order.

If no such permutation exists (i.e. when the digits are arranged in descending order), output -1.

The approach is based on the following steps:

1. Traverse the number from right to left to find the first digit \(d_i\) that is smaller than its adjacent right digit \(d_{i+1}\).
2. Find the smallest digit on the right side of \(d_i\) that is larger than \(d_i\) and swap them.
3. Reverse the order of the digits to the right of index \(i\) to obtain the next smallest lexicographical order.

inputFormat

The input consists of a single line containing a string of digits. For example: 12345.

outputFormat

Output a single integer representing the next higher number that can be formed by the digits of the input number, or -1 if no such number exists.## sample

12345

12354