Dividing the Pirate Hoard

Time limit1sMemory limit128 MB

Summary

Each of N pirates in turn splits the pile into N equal parts, keeps one part plus the remainder, and returns the rest; report each pirate's hidden coins and the leftover pile.

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

Problem

After raiding an island, $N$ pirates end up with $M$ coins. Once the raid is over, everyone gathers the coins into a single community pile, to be divided the next day.

During the night, one pirate decides to take his share early. He sneaks over to the hoard and divides the $M$ coins into $N$ equal piles, with $K$ coins left over. He keeps the extra $K$ coins for himself, hides one pile as his own share, and puts the remaining piles back together into a single pile. Each of the other pirates then does the same thing, one at a time: each divides the remaining coins into $N$ piles, takes one pile, and keeps any leftover coins so that the remaining piles stay equal in size.

Given the number of pirates and the number of coins, determine how many coins each pirate ends up with in his own hidden pile (his equal-sized pile plus the leftover coins), and how many coins remain in the community pile at the end of the night.

Input

The input consists of the number of coins $M$ , followed by the number of pirates $N$ .

Output

On the first line, print the number of coins taken by each pirate, from largest to smallest, separated by spaces. On the second line, print the total number of coins remaining in the hoard at the end of the night.

Examples2

Example 1
Input
```
12 2
```
Expected output
```
6 3
3
```
Example 2
Input
```
10 3
```
Expected output
```
4 2 2
2
```