Next Permutation of an Integer

Given a positive integer N, your task is to compute the next higher permutation of the digits of N. In other words, find the smallest integer greater than N that can be formed by reordering its digits. If no such permutation exists (i.e. if N's digits are in descending order), then output the smallest permutation by arranging the digits in ascending order.

For example, if N = 231, the next permutation is 312; if N = 987, then the answer is 789.

Your solution should read the input from stdin and write the result to stdout.

inputFormat

The input consists of a single line containing a positive integer N.

outputFormat

Output a single integer which is the next permutation of N if it exists; otherwise, output the smallest permutation of N's digits.

231

312