Walaweh

Walaweh 수는 일부러 성가시게 만든 번호 매기기 수열의 한 항목입니다. 이름도 바로 그 성가심에서 왔습니다("Walaweh!"). Walaweh 수는 0과 1만 사용한다는 점에서 이진수처럼 보이지만, 보통의 이진수와 달리 자릿수(길이)가 중요해서 앞자리의 0을 그대로 보존합니다. 여기서 Walaweh 수의 길이란 단순히 자릿수를 뜻합니다.

표기를 간단히 하기 위해, 길이가 $L$인 Walaweh 수들을 $W_L$로 씁니다. 이는 정확히 $L$자리인 모든 Walaweh 수를 순서대로 나열한 목록입니다. 가장 작은 $W_1$은 고정되어 있으며, 순서대로 "0"과 "1" 두 수입니다. $L \ge 2$일 때 $W_L$은 $W_{L-1}$로부터 만들어집니다. 먼저 $W_{L-1}$의 복제본 $C_1$과 $C_2$를 만들고, 아래에서 정한 연산 하나를 적용해 이들을 각각 $C_1'$과 $C_2'$로 바꾼 뒤, 목록 $C_1'$ 다음에 목록 $C_2'$를 이어 붙이면 $W_L$이 됩니다.

$C_1$과 $C_2$에 적용할 수 있는 연산은 다음 8가지입니다.

1. $C_1$의 모든 수 끝에 숫자 0을 붙이고, $C_2$의 모든 수 끝에 숫자 1을 붙입니다.
2. $C_1$의 모든 수 앞에 숫자 0을 붙이고, $C_2$의 모든 수 앞에 숫자 1을 붙입니다.
3. $C_1$의 모든 수 끝에 숫자 1을 붙이고, $C_2$의 모든 수 끝에 숫자 0을 붙입니다.
4. $C_1$의 모든 수 앞에 숫자 1을 붙이고, $C_2$의 모든 수 앞에 숫자 0을 붙입니다.
5. 목록 $C_2$의 순서를 뒤집은 다음 연산 1을 적용합니다.
6. 목록 $C_2$의 순서를 뒤집은 다음 연산 2를 적용합니다.
7. 목록 $C_2$의 순서를 뒤집은 다음 연산 3을 적용합니다.
8. 목록 $C_2$의 순서를 뒤집은 다음 연산 4를 적용합니다.

연산은 순환하며 반복됩니다. $W_1$은 고정입니다. $W_2$는 $W_1$에 연산 1을, $W_3$은 $W_2$에 연산 2를 적용해 얻으며, 이런 식으로 진행하다가 연산 8 다음에는 다시 연산 1로 돌아갑니다. 따라서 $W_9$는 $W_8$에 연산 8을, $W_{10}$은 $W_9$에 연산 1을 적용한 결과이고, 이후로도 같은 방식으로 이어집니다. Walaweh!

다음은 $W_1$, $W_2$, $W_3$, $W_4$입니다.

$W_1$

$W_2$

$W_3$

$W_4$

연산 5~8에서 쓰이는 "목록 $C_2$의 순서 뒤집기"를 보여 주기 위해, $W_6$의 마지막 5개 수를 제시합니다.

$W_6$

길이와 순번이 주어지면 Walaweh 수를 구하고, 반대로 Walaweh 수가 주어지면 순번을 구하세요.

입력은 하나 이상의 질의로 이루어지며, 각 질의는 한 줄에 하나씩 파일 끝까지 주어집니다. 각 줄은 다음 두 형식 중 하나입니다.

• Walaweh L N — 길이 $L$($1 \le L < 64$)과 순번 $N$($1 \le N \le 2^L$).
• Sequence S — Walaweh 수의 이진 문자열 $S$이며, 그 길이는 64 미만입니다(길이는 $S$ 자체로부터 알 수 있습니다).

Walaweh L N 줄에 대해서는 길이가 $L$인 Walaweh 수 중 $N$번째 수를, 앞자리 0을 그대로 포함해 정확히 $L$자리로 출력하세요. Sequence S 줄에 대해서는 Walaweh 수 $S$의 순번을 출력하세요. 각 입력 줄마다 한 개의 답을 입력과 같은 순서로 출력합니다.