Strings are usually ordered in lexicographical order. That means they are ordered by comparing their leftmost different characters. For example, because . Also because . If one string is an exact prefix of the other it is lexicographically smaller, e.g., .
Given an array of strings sorted in lexicographical order, print all of its permutations in strict lexicographical order. If two permutations look the same, only print one of them. See the 'note' below for an example.
Complete the function next_permutation which generates the permutations in the described order.
For example, . The six permutations in correct order are:
ab bc cd ab cd bc

Sample Input 0


Sample Output 0


Explanation 0