7799번 - Walaweh 다국어

Walaweh number is a numbering sequence that is so troublesome (that's exactly where it gets its name, "Walaweh!"). Walaweh number is similar to binary number (only consist of zeros and ones) except that the length of the number is important (thus leading zeros are preserved). Note that the "length" of Walaweh numbers means the number of digits in the Walaweh numbers.

To simplify the wording, Walaweh numbers of length L will be written as WL, which denotes all Walaweh numbers with exactly L digits. Walaweh numbers (of any length) is an ordered list of numbers. The most basic (smallest) Walaweh numbers is W1 which are "0" and "1" in that order. WL can be generated from WL-1 except for W1 which is fixed. This is done by creating two clones (C1 and C2) of WL-1 then apply some operations (see below) on C1 and C2 to produce C1' and C2'. The combined list of numbers in C1' followed by the list of numbers in C2' (in that order) produces WL.

These are the 8 possible operations on C1 and C2:

1. Append a digit zero to the end of all numbers in C1 and append a digit one to the end of all numbers in C2.
2. Append a digit zero to the beginning of all numbers in C1 and append a digit one to the beginning of all numbers in C2.
3. Append a digit one to the end of all numbers in C1 and append a digit zero to the end of all numbers in C2.
4. Append a digit one to the beginning of all numbers in C1 and append a digit zero to the beginning of all numbers in C2.
5. Reverse the order of the list of numbers in C2 and do operation 1 above.
6. Reverse the order of the list of numbers in C2 and do operation 2 above.
7. Reverse the order of the list of numbers in C2 and do operation 3 above.
8. Reverse the order of the list of numbers in C2 and do operation 4 above.

W1 is fixed. W2 is generated by applying the first operation on W1. W3 is generated by applying the second operation on W2 and so on... and it will go back to the first operation again after the eighth operation. So, W9 is generated by applying the eighth operation on W8. W10 is generated by applying the first operation on W9 and so on... Walaweh!

Below is the list of W1, W2, W3, and W4 :

To give you an idea of "reverse the order of the list of numbers in C2" for the fifth to eighth operations, we give the last 5 numbers of W6 :

Your job is to convert from Walaweh Length + Sequence Number into Walaweh Number and vice versa.

There are multiple input, each on a line by itself. The line will either begin with the word "Walaweh" then followed by an integer number L < 64 and N < 2^L or begin with the word "Sequence" then followed by a binary representation of the Walaweh number with length < 64.

For input line that begins with "Walaweh" you have to output the N'th Walaweh number of length L. For those lines that begins with "Sequence" you have to output the Sequence number of the given Walaweh number (The length of the Walaweh number is already obvious from the input).