마법구슬 timer 1초 memory 256MB

해리포터는 마법의 성의 방들에 있는 보물들을 최대한 많이 가져올 계획을 세우고 있다. 

마법의 성에는 일렬로 되어 있는 N=2^m개의 방이 있으며, 모든 방에는 보물이 하나씩 존재한다. 

이 방들에는 문이 없고 출입하기 위해서는 마법 구슬을 이용하는 길밖에 없다.

해리포터에게는 N+1개의 마법 구슬이 있는데 IN으로 표시되는 마법 구슬과 

A₁, A₂, ..., A_n-1으로 표시되는 N-1개의 마법 구슬과 OUT으로 표시되는 마법 구슬이 있다. 

각 마법 구슬들은 다음과 같은 특징을 가진다.

• 마법 구슬 IN은 항상 제일 먼저 사용해야 하는 구슬이며, 해리포터를 N개의 방들 중 임의의 어느 한 방에 처음으로 들어가게 한다. (단, 어느 방에 들어가게 될지는 미리 알 수 없지만, 들어간 다음에는 그 방의 번호를 알 수 있다.)

• 마법 구슬 A_k(1≤k≤N-1)는 임의의 방에 있는 해리포터를 왼쪽 또는 오른쪽으로 k만큼 떨어진 방안으로 이동하게 한다. 왼쪽으로 이동할지 오른쪽으로 이동할지는 해리포터가 지정할 수 있다.

• 마법 구슬 OUT은 제일 마지막에 사용해야 하는 구슬이며, 해리포터를 마법의 성에 있는 방으로부터 탈출하게 한다.

• 모든 마법 구슬 IN, A_k(1≤k≤N-1), 및 OUT은 한 개씩만 주어져 있고, 한번 사용하고 나면 없어져서 다시 사용할 수 없다.

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

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

• A₁을 사용하여 2번 방으로 간다.

• A₂를 사용하여 4번 방으로 간다.

• A₃를 사용하여 1번 방으로 간다.

• OUT을 사용하여 탈출한다.

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

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

• A₃를 사용하여 4번 방으로 간다.

• A₂를 사용하여 2번 방으로 간다.

• A₁을 사용하여 3번 방으로 간다.

• OUT을 사용하여 탈출한다.

마법의 성에 있는 방들의 개수 N과 해리포터가 IN을 사용하여 들어간 방의 위치가 주어졌을 때, 

그가 마법 구슬 A₁ A₂ ... A_n-1및 OUT을 이용해서 방들에 있는 보물을 

최대한 많이 찾아 가져오기 위하여 들어간 방의 순서를 구하는 프로그램을 작성하시오.