Weird Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Convert numbers between decimal and a given negative base representation, in both directions, for multiple queries until an end marker.

Level: Medium4 of 10
Topics: Math, Implementation, Simulation
Solved: No attempts yet

Problem

Binary numbers form the principal basis of computer science. Most people have heard of other systems, such as ternary, octal, or hexadecimal, and know how to use them and convert numbers between them. But did you know that the base (radix) of a number system can also be negative? A university lecturer recently encountered negabinary numbers and other systems with a negative base. Will you help convert numbers to and from these systems?

A number written in a system with a positive base $R$ is a string of digits between $0$ and $R-1$ inclusive. A digit at position $P$ (positions are counted from right to left, starting at zero) represents a value of $R^{P}$ : the digit is multiplied by $R^{P}$ , and the values of all positions are summed. For example, in the octal system ( $R = 8$ ) the number $17024$ has the value

$1\times 8^{4} + 7\times 8^{3} + 0\times 8^{2} + 2\times 8^{1} + 4\times 8^{0} = 4096 + 3584 + 16 + 4 = 7700.$

With a negative radix $-R$ the principle is the same: a digit at position $P$ has a value of $(-R)^{P}$ . For example, the number $17024$ in base $-8$ equals

$1\times(-8)^{4} + 7\times(-8)^{3} + 0\times(-8)^{2} + 2\times(-8)^{1} + 4\times(-8)^{0} = 4096 - 3584 - 16 + 4 = 500.$

One big advantage of a negative base is that no minus sign is needed to write negative numbers. Here are some examples for the negabinary system ( $R = -2$ ):

decimal	negabinary	decimal	negabinary	decimal	negabinary
-10	1010	-3	1101	4	100
-9	1011	-2	10	5	101
-8	1000	-1	11	6	11010
-7	1001	0	0	7	11011
-6	1110	1	1	8	11000
-5	1111	2	110	9	11001
-4	1100	3	111	10	11110

When no leading zeros are allowed, the representation of any integer in a negative base is unique; the only number that may start with the digit 0 is zero itself.

Input

The input contains several conversions, one per line.

A conversion from decimal to a negative-base system begins with the lowercase word to, immediately followed (no space) by a minus sign and the base $R$ , then one space and a decimal number $N$ . For example, to-2 10 asks for $10$ written in base $-2$ .

A conversion to decimal begins with the lowercase word from, immediately followed by a minus sign and the base $R$ , then one space and a number written in base $-R$ . For example, from-2 1010 asks for the decimal value of $1010$ read in base $-2$ .

The input ends with a line containing the lowercase word end. All numbers satisfy $2 \le R \le 10$ and $-1{,}000{,}000 \le N \le 1{,}000{,}000$ (in decimal).

Output

For each conversion, print one number on its own line. If the conversion started from decimal, print the same value written in base $-R$ . If the conversion was to decimal, print the decimal value.

Neither the input nor the output numbers contain leading zeros. A minus sign - may appear only with a negative number written in decimal; any non-negative number, or any number written in a negative base, must not begin with one.

Examples6

Example 1

Input

to-2 10
from-2 1010
to-10 10
to-10 -10
from-10 10
end

Expected output

Example 2

Input

to-2 0
from-2 0
to-10 0
from-10 0
end

Expected output

Example 3
Input
```
from-8 17024
to-8 500
end
```
Expected output
```
500
17024
```

Example 4

Input

to-2 -10
to-2 -5
to-2 6
to-2 -1
to-2 1
end

Expected output

Example 5

Input

from-2 11011
from-2 11000
from-2 11110
from-2 11
end

Expected output

Example 6
Input
```
to-5 -100
end
```
Expected output
```
1100
```