Walaweh

Time limit1sMemory limit128 MB

Summary

Each Walaweh list W_L is built from W_{L-1} by a fixed 8-step cycle of append/prepend and optional reversal operations; convert between (length, index) and the binary string. The recursion only needs O(log N) work per level, but the reversal and leading-zero handling make the index bit-mapping non-obvious.

Level: Hard8 of 10
Topics: Recursion, Bit manipulation, Math, Implementation
Solved: No attempts yet

Problem

A Walaweh number is an entry in a numbering sequence that is deliberately troublesome — which is exactly where the name comes from ("Walaweh!"). A Walaweh number looks like a binary number (it uses only the digits 0 and 1), but unlike an ordinary binary number its length matters, so leading zeros are kept. Here the length of a Walaweh number is simply its number of digits.

To keep the notation short, the Walaweh numbers of length $L$ are written $W_L$ : the ordered list of every Walaweh number with exactly $L$ digits. The smallest one, $W_1$ , is fixed and equals the two numbers "0" and "1", in that order. For $L \ge 2$ , $W_L$ is generated from $W_{L-1}$ : make two clones $C_1$ and $C_2$ of $W_{L-1}$ , apply one operation (chosen as described below) to turn them into $C_1'$ and $C_2'$ , then concatenate the list $C_1'$ followed by the list $C_2'$ to obtain $W_L$ .

There are 8 possible operations on $C_1$ and $C_2$ :

Append digit 0 to the end of every number in $C_1$ , and append digit 1 to the end of every number in $C_2$ .
Prepend digit 0 to the beginning of every number in $C_1$ , and prepend digit 1 to the beginning of every number in $C_2$ .
Append digit 1 to the end of every number in $C_1$ , and append digit 0 to the end of every number in $C_2$ .
Prepend digit 1 to the beginning of every number in $C_1$ , and prepend digit 0 to the beginning of every number in $C_2$ .
Reverse the order of the list $C_2$ , then apply operation 1.
Reverse the order of the list $C_2$ , then apply operation 2.
Reverse the order of the list $C_2$ , then apply operation 3.
Reverse the order of the list $C_2$ , then apply operation 4.

The operations are used in a repeating cycle. $W_1$ is fixed; $W_2$ is obtained by applying operation 1 to $W_1$ , $W_3$ by applying operation 2 to $W_2$ , and so on, wrapping back to operation 1 after operation 8. Thus $W_9$ comes from operation 8 applied to $W_8$ , $W_{10}$ from operation 1 applied to $W_9$ , and so forth. Walaweh!

Here are $W_1$ , $W_2$ , $W_3$ , and $W_4$ :

$W_1$

Sequence Number	Walaweh Number
1	0
2	1

$W_2$

Sequence Number	Walaweh Number
1	00
2	10
3	01
4	11

$W_3$

Sequence Number	Walaweh Number
1	000
2	010
3	001
4	011
5	100
6	110
7	101
8	111

$W_4$

Sequence Number	Walaweh Number
1	0001
2	0101
3	0011
4	0111
5	1001
6	1101
7	1011
8	1111
9	0000
10	0100
11	0010
12	0110
13	1000
14	1100
15	1010
16	1110

To illustrate "reverse the order of the list $C_2$ " used by operations 5–8, here are the last 5 numbers of $W_6$ :

$W_6$

Sequence Number	Walaweh Number
60	110011
61	101111
62	100111
63	101011
64	100011

Your task is to convert a length together with a sequence number into the Walaweh number, and vice versa.

Input

The input contains one or more queries, one per line, until end of file. Each line has one of two forms:

Walaweh L N — a length $L$ with $1 \le L < 64$ and a sequence number $N$ with $1 \le N \le 2^L$ .
Sequence S — the binary string $S$ of a Walaweh number, whose length is less than 64 (the length is evident from $S$ itself).

Output

For every Walaweh L N line, output the $N$ -th Walaweh number of length $L$ , printed with its leading zeros so that it has exactly $L$ digits. For every Sequence S line, output the sequence number of the Walaweh number $S$ . Print one answer per input line, in the same order as the input.

Examples1

Example 1

Input

Walaweh 1 1
Walaweh 3 6
Walaweh 4 13
Sequence 1100
Walaweh 5 14
Sequence 1110
Sequence 01010
Walaweh 6 1
Walaweh 6 20
Walaweh 6 32

Expected output