Positional number systems

Time limit1sMemory limit1024 MB

Summary
Write integer R in a positional base B, which may be negative, fractional, or a reciprocal of an integer.
Level

Medium4 of 10

Topics
Math, Implementation, Number theory, Simulation
Solved
No attempts yet

Problem

We are used to writing numbers in decimal. Writing "123" really means 1⋅102+2⋅10+31 \cdot 10^2 + 2 \cdot 10 + 3.

Binary shows up often too. The binary form of 123123 is "1111011", which means 1⋅26+1⋅25+1⋅24+1⋅23+0⋅22+1⋅2+11 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2 + 1.

The base of a positional system does not have to be a natural number. Written in base −10-10, the number 123123 becomes "283", which means 2⋅(−10)2+8⋅(−10)+32 \cdot (-10)^2 + 8 \cdot (-10) + 3.

The base does not even have to be an integer. In base 2.52.5 the number 123123 is written "22122.02012122…\ldots", where the part after the point runs on forever to the right.

Bases smaller than 11 make sense as well. In such a system the notation comes out mirrored, because place values grow as you move right from the point. In base 0.10.1 the number 123123 is written "3.21", which means 3+2⋅0.1−1+1⋅0.1−23 + 2 \cdot 0.1^{-1} + 1 \cdot 0.1^{-2}.

You are given an integer RR and a base BB. Print the representation of RR in base BB.

Input

The first line has the integer RR in decimal (0≤R≤1010−10 \le R \le 10^{10} - 1), at most 1010 digits.

The second line has the base BB in decimal. Either BB is an integer with 2≤∣B∣≤102 \le |B| \le 10, or 1/B1/B is an integer with 2≤∣1/B∣≤102 \le |1/B| \le 10.

Output

Let b=Bb = B when ∣B∣>1|B| > 1, and b=1/Bb = 1/B when ∣B∣<1|B| < 1. In both cases bb is an integer, and the representation uses the digits 00 to ∣b∣−1|b| - 1.

When ∣B∣>1|B| > 1, print the digits of RR in base BB on one line, from the highest place value down to the B0B^0 place. Print no point and no leading zero.

When ∣B∣<1|B| < 1, print the digit of the B0B^0 place first, then a point, then the digits of the B−1B^{-1}, B−2B^{-2}, …\ldots places. The last digit printed is not 00. If there is only one digit, print it without a point.

If R=0R = 0, print "0".

Exactly one representation follows these rules, and it equals RR with no rounding.

Examples3

  1. Example 1

    Input
    123
    0.1
    
    Expected output
    3.21
    
  2. Example 2

    Input
    123
    -10
    
    Expected output
    283
    
  3. Example 3

    Input
    123
    2
    
    Expected output
    1111011