### ACM-ICPC INC 2008 Final Round

## Problem H

# Walaweh

Time Limit: 8s

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 :

Walaweh Length | Sequence Number | Walaweh Numbers
--- | --- | ---
1 | 1. | 0
1 | 2. | 1
2 | 1. | 00
2 | 2. | 10
2 | 3. | 01
2 | 4. | 11
3 | 1. | 000
3 | 2. | 010
3 | 3. | 001
3 | 4. | 011
3 | 5. | 100
3 | 6. | 110
3 | 7. | 101
3 | 8. | 111

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

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 :

Walaweh Length | Sequence Number | Walaweh Numbers
--- | --- | ---
6 | 60. | 110011
6 | 61. | 101111
6 | 62. | 100111
6 | 63. | 101011
6 | 64. | 100011

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

## Input

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 < 2L or begin with the word "Sequence" then followed by a binary representation of the Walaweh number with length < 64.

## Output

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).

## Sample 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
    Sequence 100101
    Walaweh 6 40
    Walaweh 6 64
    Walaweh 7 29
    Sequence 0000001
    Walaweh 7 100
    Walaweh 15 1984
    Sequence 00100101010001
    Sequence 100101010001001001001001
    Walaweh 20 38299
    Walaweh 40 38294828288
    Sequence 10100010001001001001
    Walaweh 63 78487827863828368
    Sequence 000011100010101010010100010010010101001001001011001010001001001

## Sample Output

    0
    110
    1000
    14
    11100
    16
    31
    100010
    001110
    011100
    54
    000001
    100011
    0010000
    40
    1010000
    011011000111110
    10018
    6619354
    01101010001001010001
    0101001011111100010001001010000001000001
    350619
    010000110001110011110100010111111001000111000100111100101100010
    2769960758748826002