All you have to do is implement the following algorithm, which is a very popular compression technique.

1. You are given an input string A. (For example ababc)
2. Find all the rotations of A (In this case, they are ababc, babca, abcab, bcaba, cabab)
3. Now sort them (After sorting, we have ababc, abcab, babca, bcaba, cabab)
4. Then arrange them as follows:
   • ababc
   • abcab
   • babca
   • bcaba
   • cabab
5. Now pick out the last column. It is ‘cbaab’. This is the result of this algorithm.
6. Also observe that the 1st row has the original string. (Use 1 indexing)

Now, for this problem, you are given the output and the row number that has the original string. For the above example, it is ‘cbaab’ and 1.

Given these 2 parameters, you just need to decode it. (i.e. find the original string.)

Input:

Each test case has 2 lines.

1st line – An integer R that represents the row that contains the original string.

2nd line - A string that represents the output of the above algorithm. (Length of string <=2000) (All characters are lower case).

The input is terminated with R=-1.

Output:

The original string.

Sample

Input
1
cbaab
3
mnoag
-1
Output
ababc
mango