Binary Sequence Rotation

Time limit2sMemory limit128 MB

Summary

Given the last column of a sorted matrix of all circular rotations of an unknown binary string, reconstruct the lexicographically smallest rotation (first row) or report impossibility.

Level: Hard8 of 10
Topics: String matching, Sorting, String, Math
Solved: No attempts yet

Problem

Consider a binary sequence of length N. If the sequence is rotated circularly by one position at a time, it produces N rotated sequences in total. Some of those rotations may be identical.

Sort those rotated sequences in lexicographic order, equivalently by their binary values, and place them as the rows of a matrix. For example, sorting the rotations of 00011 gives the following matrix.

Now read the last column of the matrix from top to bottom. This gives one binary sequence of length N. In the matrix above, the sequence is 10010.

Given the binary sequence obtained from the last column, find the first row of such a rotation matrix if it can be made. If no binary sequence can produce such a matrix, output -1.

Input

The first line contains a natural number N. (1 <= N <= 50,000)

The second line contains a binary sequence of length N with no spaces.

Output

Print the binary sequence that appears in the first row of the rotation matrix, without spaces. If no valid rotation matrix can be made, print -1.

Examples1

Example 1
Input
```
5
10010
```
Expected output
```
00011
```