Next Permutation

Given a string \(S\), the task is to compute its next lexicographical permutation. In other words, find the smallest string greater than \(S\) that can be formed by rearranging its characters. If \(S\) is already the highest permutation, then return the lowest permutation (i.e., the characters sorted in ascending order).

The algorithm involves identifying the pivot where the next greater element can be swapped and then reversing the suffix to get the minimum possible sequence. This problem is a classic and requires careful manipulation of the string.

inputFormat

A single line containing the string (S).

outputFormat

Output a single line containing the next permutation of the string (S).## sample

ABCD

ABDC