Lexicographic Permutations

Given an integer \( n \) and a string message of length \( n \), your task is to generate all possible permutations of the characters in the string in lexicographic order.

The lexicographic order is defined as follows: For two different strings \( s_1 \) and \( s_2 \), we say \( s_1 < s_2 \) if there exists an index \( k \) such that for all \( i < k \), \( s_1[i] = s_2[i] \) and \( s_1[k] < s_2[k] \). In other words, the strings are compared character by character from left to right.

Your program should read from standard input and output the permutations to standard output, one permutation per line.

inputFormat

The input consists of two lines:

1. The first line contains an integer \( n \) representing the length of the string.
2. The second line contains the string message which consists of exactly \( n \) characters.

outputFormat

Output all the permutations of the given string in lexicographic order, each on a separate line.

## sample

3
abc

abc
acb
bac
bca
cab
cba

</p>