Geek Challenge [SKRZAT] (Base Minus Two)

Interview

Time limit1sMemory limit128 MB

Summary

Convert numbers between decimal and base -2 (Weird Binary), echoing each query with its formatted result.

Level: Easy3 of 10
Topics: Math, Implementation, Number theory
Solved: No attempts yet

Problem

Geek Challenge [SKRZAT] is a very old game from Poland, played on a console with two buttons and a joystick. True to its name, the game communicates in binary: one button means zero and the other means one. It goes one step further and uses a number system whose base is minus two instead of plus two — a representation we will call “Weird Binary”.

In Weird Binary the bit in position $i$ (counted from the right, starting at $0$ ) has weight $(-2)^i$ . The value of a bit string is the sum of the weights of the positions that hold a one. The five-bit patterns and their values are:

Every five-bit pattern, ordered by bit pattern:

Bits	Value	Bits	Value	Bits	Value	Bits	Value
00000	0	01000	-8	10000	16	11000	8
00001	1	01001	-7	10001	17	11001	9
00010	-2	01010	-10	10010	14	11010	6
00011	-1	01011	-9	10011	15	11011	7
00100	4	01100	-4	10100	20	11100	12
00101	5	01101	-3	10101	21	11101	13
00110	2	01110	-6	10110	18	11110	10
00111	3	01111	-5	10111	19	11111	11

The same values, ordered by magnitude:

Bits	Value	Bits	Value	Bits	Value	Bits	Value
01010	-10	00010	-2	11010	6	10010	14
01011	-9	00011	-1	11011	7	10011	15
01000	-8	00000	0	11000	8	10000	16
01001	-7	00001	1	11001	9	10001	17
01110	-6	00110	2	11110	10	10110	18
01111	-5	00111	3	11111	11	10111	19
01100	-4	00100	4	11100	12	10100	20
01101	-3	00101	5	11101	13	10101	21

Numbers appear on the screen in Weird Binary, and the player answers from the console with a stream of zeroes and ones. Write a program that helps a novice by translating numbers between decimal and Weird Binary.

Input

The first line contains a single integer $n$ , the number of queries. Each of the next $n$ lines is one query:

a line beginning with b contains a Weird Binary string that must be converted to decimal;
a line beginning with d contains a decimal integer that must be converted to Weird Binary.

Every value fits in a 15-bit Weird Binary number, so the decimal range is $-10922$ to $21845$ inclusive.

Output

Print one line per query, echoing the query type and its input string together with the converted result:

for a b query: From binary: <string> is <decimal>
for a d query: From decimal: <string> is <weird binary>

Reproduce the input string exactly (a Weird Binary input may contain leading zeroes). In a produced Weird Binary result leading zeroes are not allowed, and the value $0$ is written as 0. Match the spacing shown above exactly.

Examples1

Example 1

Input

10
b 1001101
b 0111111
b 101001000100001
b 010010001000010
b 100110100110100
d -137
d 137
d 8191
d -10000
d 21000

Expected output

From binary: 1001101 is 61
From binary: 0111111 is -21
From binary: 101001000100001 is 19937
From binary: 010010001000010 is -7106
From binary: 100110100110100 is 15604
From decimal: -137 is 10001011
From decimal: 137 is 110011001
From decimal: 8191 is 110000000000011
From decimal: -10000 is 10100100110000
From decimal: 21000 is 101011000011000