시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2361047851.656%

문제

해리포터는 마법의 성의 방들에 있는 보물들을 최대한 많이 가져올 계획을 세우고 있다. 마법의 성에는 일렬로 되어있는 N = 2m개의 방이 있으며, 모든 방에는 보물이 하나씩 존재한다. 이 방들에는 문이 없고 출입하기 위해서는 마법 구슬을 이용하는 길밖에 없다.

해리포터에게는 N+1개의 마법 구슬이 있는데, IN으로 표시되는 마법 구슬과 A1, A2, ..., AN-1으로 표시되는 N-1개의 마법 구슬과 OUT으로 표시되는 마법 구슬이 있다. 각 마법 구슬들은 다음과 같은 특징을 가진다.

  • 마법 구슬 IN은 항상 제일 먼저 사용해야 하는 구슬이며, 해리포터를 N개의 방들 중 임의의 어느 한 방에 처음으로 들어가게 한다. (단, 어느 방에 들어가게 될지는 미리 알 수 없지만, 들어간 다음에는 그 방의 번호를 알 수 있다.)
  • 마법 구슬 Ak(1 ≤ k ≤ N-1)는 임의의 방에 있는 해리포터를 왼쪽 또는 오른쪽으로 k 만큼 떨어진 방안으로 이동하게 한다. 왼쪽으로 이동할지 오른쪽으로 이동할지는 해리포터가 지정할 수 있다.
  • 마법 구슬 OUT은 제일 마지막에 사용해야 하는 구슬이며, 해리포터를 마법의 성에 있는 방으로부터 탈출하게 한다.
  • 모든 마법 구슬 IN, Ak(1 ≤ k ≤ N-1), 및 OUT은 한 개씩만 주어져 있고, 한번 사용하고 나면 없어져서 다시 사용할 수 없다.

예를 들어, N=4인 경우에 IN, A1, A2, A3, 및 OUT의 총 5개의 마법 구슬들이 해리포터에게 주어져 있고, IN을 사용했더니 3번방에 들어가게 되었다고 하자.

이때, 그는 다음과 같은 방법으로 마법 구슬을 이용하여 방들에 있는 4개의 보물을 찾아 가져올 수 있다.

  • A1을 사용하여 2번 방으로 간다.
  • A2를 사용하여 4번 방으로 간다.
  • A3를 사용하여 1번 방으로 간다.
  • OUT을 사용하여 탈출한다. 

또 다른 예로, N=4인 경우에 IN을 이용했더니 1번방에 들어가게 되었다고 하자.

이때는 다음의 방법으로 방들에 있는 4개의 보물을 찾아 가져올 수 있다.

  • A3를 사용하여 4번 방으로 간다.
  • A2를 사용하여 2번 방으로 간다.
  • A1을 사용하여 3번 방으로 간다.
  • OUT을 사용하여 탈출한다. 

마법의 성에 있는 방들의 개수 N과 해리포터가 IN을 사용하여 들어간 방의 위치가 주어졌을 때, 그가 마법 구슬 A1, ⋯, AN-1및 OUT을 이용해서 방들에 있는 보물을 최대한 많이 찾아 가져오기 위하여 들어간 방의 순서를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 개수를 나타내는 정수 N (단, 21 ≤ N ≤ 213=8192)이 주어진다. N은 2의 거듭제곱인 정수이다. 둘째 줄에는 해리 포터가 IN을 사용해 들어간 방의 번호를 나타내는 정수 M이 주어진다. (단, 1 ≤ M ≤ N)

출력

해리 포터가 처음 들어간 방에서 시작하여, 방들에 있는 보물을 최대한 많이 찾아오기 위하여 들어간 방 번호들을 순서대로 한 줄에 출력한다. 각 방 번호사이에는 빈칸을 한개 둔다. 답이 여러 개인 경우에는 그 중 하나만 출력한다.

예제 입력 1

4
3

예제 출력 1

3 2 4 1