이진 수열 회전

시간 제한2초메모리 제한128 MB

요약

알 수 없는 이진 문자열의 모든 회전을 정렬한 행렬에서 마지막 열만 주어졌을 때 첫 행(사전순 최소 회전)을 복원하거나 불가능하면 -1을 출력합니다.

문제

길이 N인 이진 수열이 있다. 이 수열을 원형으로 한 칸씩 회전하면 모두 N개의 회전 수열을 만들 수 있다. 서로 같은 회전 수열이 여러 번 나올 수도 있다.

이 회전 수열들을 사전순, 즉 이진수 값이 작은 순서대로 정렬하여 행렬의 각 행으로 놓는다. 예를 들어 00011의 회전 수열들을 정렬하면 다음 행렬이 된다.

그 뒤 행렬의 마지막 열을 위에서 아래로 읽으면 길이 N인 이진 수열 하나를 얻는다. 위 행렬에서는 10010을 얻는다.

마지막 열을 읽어 얻은 이진 수열이 주어졌을 때, 이러한 회전 행렬을 만들 수 있다면 그 행렬의 첫 번째 행을 구하라. 어떤 이진 수열로도 그런 행렬을 만들 수 없다면 -1을 출력하라.

첫째 줄에 자연수 N이 주어진다. (1 <= N <= 50,000)

둘째 줄에 길이 N인 이진 수열이 공백 없이 주어진다.

회전 행렬의 첫 번째 행이 되는 이진 수열을 공백 없이 출력한다. 만들 수 있는 회전 행렬이 없다면 -1을 출력한다.