noiHa의 탑

루카스는 여섯 살짜리 아들이 기초 알고리즘을 배울 준비가 되었다고 생각한다. 그는 가장 아름다운 기법 중 하나인 재귀를 먼저 가르치기로 하고, 이를 보여 주려고 잘 알려진 재귀 게임인 하노이의 탑을 골랐다.

하노이의 탑은 막대 세 개와 지름이 서로 다른 원판 여러 개로 이루어진 수학 게임이다. 원판은 어느 막대에든 끼울 수 있다. 처음에는 모든 원판이 크기 순서대로 첫 번째 막대에 쌓여 있고, 가장 작은 원판이 맨 위에 있어 전체 모양이 원뿔에 가깝다. 목표는 다음 규칙을 지키면서 쌓인 원판 전체를 마지막 막대로 옮기는 것이다.

• 한 번에 원판 하나만 옮길 수 있다.
• 각 이동에서는 어느 막대의 맨 위 원판을 가져와 다른 막대의 맨 위나 빈 막대에 놓는다.
• 원판을 자기보다 작은 원판 위에 놓을 수 없다.

하노이의 탑을 푸는 데 필요한 최소 이동 횟수가 $2^n - 1$이라는 것을 루카스는 알고 있다. 여기서 $n$은 원판의 개수다. 최적 이동은 하나로 정해지므로, 항상 최적으로 움직인다고 가정하면 $n$과 지금까지 한 이동 횟수만으로 게임의 현재 상태가 정해진다.

루카스는 아들에게 게임 푸는 법을 한 단계씩 보여 주고 있었다. 지금까지 최적 이동을 $k$번 했다. 아직 끝내려면 시간이 더 걸려서, 잠깐 간식을 가지러 자리를 비웠다. 돌아와 보니 장난꾸러기 아들이 큰 "이동"을 한 뒤였다. 아들은 목표가 첫 번째 막대의 원판을 모두 마지막 막대로 옮기는 것임을 알고 있었지만, 원판의 순서를 바꾸지 않은 채 "첫 번째 막대의 원판 전부를 마지막 막대로 옮기기"를 이동 한 번으로 해 버렸다. 그림 K.1을 보라.

그림 K.1: 아들의 큰 "이동" 전후의 게임 배치.

루카스는 이것도 가르칠 기회로 삼을 수 있다고 생각한다. 그는 "유효한" 이동만 사용해서 게임을 풀기로 했다. 다만 지금 상태에서 최소 몇 번이면 끝낼 수 있는지 알고 싶어 한다. 아들을 돌보느라 바쁘니 여러분의 도움이 필요하다.

주어진 상태가 올바르지 않더라도 "유효한" 이동의 정의는 그대로 적용된다. 즉, 한 번에 맨 위 원판 하나만 옮길 수 있고, 자기보다 작은 원판 위에는 놓을 수 없다. 특히 크기가 $a$인 원판을 크기가 $b$인 원판이 있는 막대 위에 놓는 것은, 이 막대의 맨 위 원판 크기가 $c$이고 $a < c$이면 유효하다 (단, $b < a$).

첫 번째 줄에는 게임의 원판 개수 $n$이 주어진다 ($1 \le n \le 200\,000$).

두 번째 줄에는 큰 이동을 하기 전에 루카스가 수행한 최적 이동 횟수 $k$가 주어진다 ($0 \le k \le 2^n - 1$). $k$는 이진수로 주어진다.

게임을 끝내는 데 필요한 최소 이동 횟수를 이진수로 한 줄에 출력한다.