Dividing the Digits of an Integer in Base k

Interview

Time limit1sMemory limit512 MB

Summary

Convert n to base k, split its digits at each 0, and print the sum of the distinct nonempty pieces in base k.

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

Problem

You are given positive integers $n$ and $k$ . Let $a$ be $n$ written in base $k$ . Split each digit of $a$ at the digit 0, and let $b$ be the set of the resulting numbers. A piece that is empty because of consecutive zeros is not included in $b$ . Print the sum of the numbers in $b$ in base $k$ . For example, if $n = 19$ and $k = 2$ , then $a = 100112$ , $b$ contains 1 and 11, and $1 + 11 = 12 = 1100_2$ , so the output is 1100.

Input

The first line contains the positive integers $n$ and $k$ , separated by a space.

Output

On the first line, print the sum of the numbers in $b$ written in base $k$ .

Constraints

$1 \le n \le 1{,}000{,}000$ , $2 \le k \le 10$

Examples4

Example 1
Input
```
437674 3
```
Expected output
```
22101
```
Example 2
Input
```
29 3
```
Expected output
```
10
```
Example 3
Input
```
11 3
```
Expected output
```
10
```
Example 4
Input
```
3 3
```
Expected output
```
1
```