1199 - Walaweh

Time Limit : 8 Second

Memory Limit : 128 MB

Submission: 11

Solved: 9

Description


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 LengthSequence NumberWalaweh Numbers
11.0
12.1

 

21.00
22.10
23.01
24.11

 

31.000
32.010
33.001
34.011
35.100
36.110
37.101
38.111




Walaweh LengthSequence NumberWalaweh Numbers
41.0001
42.0101
43.0011
44.0111
45.1001
46.1101
47.1011
48.1111
49.0000
410.0100
411.0010
412.0110
413.1000
414.1100
415.1010
416.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 LengthSequence NumberWalaweh Numbers
660.110011
661.101111

662.100111
663.101011
664.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

hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.