구슬 목걸이

One Martian 소년 조르그는 지구에서 온 친구 마샤에게 구슬 목걸이 하나를 선물하고 싶어 한다. 그는 마샤가 파란색과 빨간색의 두 색을 좋아한다는 것을 알고 있으며, 마침 그가 찾아온 가게에는 이 두 색의 구슬로 만든 다양한 장신구가 있다. 모든 구슬 목걸이에는 작은 잠금장치가 달려 있으며, 이를 풀어 보면 가게에 있는 모든 구슬 목걸이의 길이가 같다는 것을 알 수 있다. 화성인의 시각적 특성 때문에, 조르그가 파란색과 빨간색으로 된 구슬 목걸이 하나를 본 다음 파란색 구슬은 빨간색으로, 빨간색 구슬은 파란색으로 바뀐 다른 목걸이를 보면 두 목걸이를 동일하다고 여긴다. 다시 말해, 조르그는 목걸이를 뒤집어 서로로부터 얻을 수 있는 구슬 목걸이뿐만 아니라, 두 색을 서로 바꾸거나 목걸이를 뒤집는 것, 또는 이 두 연산을 모두 사용하여 서로로부터 얻을 수 있는 구슬 목걸이도 동일하다고 여긴다.

모든 화성인은 매우 질서정연하며, 어떤 수의 물건을 보면 이를 올바른 순서로 정리하려 한다고 알려져 있다. 조르그는 빨간색 구슬이 파란색 구슬보다 작다고 생각한다. 빨간색 구슬은 0, 파란색 구슬은 1로 나타내자. 두 목걸이에서 i-th 위치의 구슬이 파란색이고, 앞의 i - 1개 구슬이 동일하다면, 화성인은 i-th 위치에 빨간색 구슬이 있는 목걸이를 더 앞에 놓는다.

먼저 조르그는 모든 구슬 목걸이의 잠금장치를 풀고, 자신의 관점에서 동일한 목걸이끼리 각 작은 더미에 들어가도록 나눈다. 그런 다음 각 더미를 정리하고, 자신의 관점에서 각 더미의 최소 목걸이를 선택한다. 불필요한 목걸이는 점원에게 돌려주며 더는 필요하지 않다고 말한다. Then Zorg은 남은 구슬 목걸이를 정렬하고 인덱스가 k인 목걸이를 산다.

이 모든 조작에는 조르그의 시간이 많이 들기 때문에, 그는 마샤에게 줄 구슬 목걸이를 찾는 일을 도와달라고 요청한다.

입력 파일에는 두 정수 n와 k (2 ≤ n ≤ 50;1 ≤ k ≤ 1016)이 주어진다. 이는 각각 구슬 목걸이의 길이와 조르그가 선택한 목걸이의 인덱스이다.

빨간색 구슬은 0, 파란색 구슬은 1로 나타내어 k-th 구슬 목걸이를 출력한다. 필요한 목걸이를 찾을 수 없다면 유일한 수 -1을 출력한다.

길이가 4인 구슬 목걸이의 예제인 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110을 살펴보자. 조르그는 이를 다음 더미로 나눈다: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. 그런 다음 각 더미에서 최소 구슬 목걸이인 0001, 0010, 0011, 0101, 0110을 선택한다. 네 번째 목걸이는 0101이다.