Next Permutation Number

Given a positive integer \(x\), find the smallest number \(y\) such that the frequency of every digit from \(0\) to \(9\) in \(y\) is exactly the same as in \(x\) and \(x < y\). In other words, \(y\) is the next lexicographical permutation of the digits of \(x\). It is guaranteed that such a \(y\) exists for the given input.

inputFormat

The input consists of a single line containing a positive integer \(x\) (without leading zeros).

outputFormat

Output the smallest number \(y\) which is the next permutation of \(x\) such that \(x < y\).

sample

123

132