#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Problem #5: PokéAdd

After saving the world, PokéTrainer Little Joseph has nothing to do and wants to test out your programming skills, and hence you have been asked to solve this PokéTest problem set by Little Joseph.

Little Joseph will give you two integers x and y and his desired base b, and he wants to do something weird to these two integers. He wants you to convert x and y into base b then add them up in that base. However, he does not allow you to carry over the number when you add.

For example, if x = 29, y = 33 and b = 5,

Little Joseph wants you to convert x and y into base 5 to get x = 104 (b5) and y = 113 (b5).

Adding them normally would give 222 by first adding 4 and 3 to get 125, then carry over the 1 to the next place value to add to 0 + 1 to give 2. However, if carrying over is disallowed, the 1 carried over from the 4+3 will not be counted, and hence the addition for the second place value would not include the extra 1. It will be instead:

104

+ 113

----------------

212 ← The 1 does not carry over, so the second place value is just merely 0 + 1

Your task as a PokéProgrammer is to fulfil Little Joseph's weird wishes and output the answer using Little Joseph's weird addition method in base b.

Input

Three integers, x, y and base b where x, y ≤ 2147483647 and b ≤ 10

Output

The answer with Little Joseph's addition in base b.

Sample Input

35 39 7

Sample Output

34

After saving the world, PokéTrainer Little Joseph has nothing to do and wants to test out your programming skills, and hence you have been asked to solve this PokéTest problem set by Little Joseph.

Little Joseph will give you two integers x and y and his desired base b, and he wants to do something weird to these two integers. He wants you to convert x and y into base b then add them up in that base. However, he does not allow you to carry over the number when you add.

For example, if x = 29, y = 33 and b = 5,

Little Joseph wants you to convert x and y into base 5 to get x = 104 (b5) and y = 113 (b5).

Adding them normally would give 222 by first adding 4 and 3 to get 125, then carry over the 1 to the next place value to add to 0 + 1 to give 2. However, if carrying over is disallowed, the 1 carried over from the 4+3 will not be counted, and hence the addition for the second place value would not include the extra 1. It will be instead:

104

+ 113

----------------

212 ← The 1 does not carry over, so the second place value is just merely 0 + 1

Your task as a PokéProgrammer is to fulfil Little Joseph's weird wishes and output the answer using Little Joseph's weird addition method in base b.

Input

Three integers, x, y and base b where x, y ≤ 2147483647 and b ≤ 10

Output

The answer with Little Joseph's addition in base b.

Sample Input

35 39 7

Sample Output

34

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 10 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-8 ans.cpp -o pokeadd -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512