문제
우로보로스는 고대 이집트 신화에 나오는 상상의 뱀이다. 우로보로스는 자신의 꼬리를 물고 삼키는 형태로 존재한다고 한다.
우로보로스 수는 0부터 2n-1의 모든 숫자를 포함하는 이진수이며, 2n개의 비트로 이뤄진 숫자를 원의 형태로 둥글게 만들어 놓아 맨 마지막 숫자 뒤에 맨 앞의 숫자가 오게 한다. 이렇게 배치한 숫자들의 연속된 n비트를 읽게 되면 0부터 2n-1의 모든 숫자가 존재할 수 있다.
예를 들어 n=2 일때의 우로보로스 수는 0011, 0110, 1100, 1001등이 있다. 0011의 경우 다음의 그림, 표를 통해 길이가 2인 모든 이진수를 찾을 수 있음을 알 수 있다.
n이 주어졌을 때 n 비트에 대한 가장 작은 우로보로스 수에 대해서 o(n,k)를 찾는 프로그램을 작성하라. 여기서 o(n,k)란 가장 작은 n비트에 대한 우로보로스 수를 맨 앞에서 부터 읽었을 때 k번째로 읽게 되는 n자리의 이진수를 10진수로 변환한 값을 뜻한다.
입력
입력의 첫 줄에는 1이상 21이하의 숫자 n이 입력된다.
그 다음 줄부터 -1이상 2n미만의 숫자 k가 입력된다. 만약 -1이 입력되었을 경우 프로그램을 종료한다.
k는 최대 1,000개 이상 입력된다.
출력
입력에 대해 o(n, k)를 입력된 순서대로 한줄에 하나씩 출력한다.
예제
2
0
1
2
3
-1
0
1
3
2
로그인해야 코드를 작성할 수 있어요.