Binary Sequence Rotation

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.

0001100110011001000111000

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.

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.

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.