The Baker's Unit Slices

A baker shares loaves identical loaves fairly among people customers. Every customer first gets as many whole loaves as possible. What each customer is still owed, a fraction of a loaf smaller than 1, is then cut into slices of size 1/k (a "unit slice") like this:

• choose the largest unit slice 1/k that is not more than what the customer is still owed,
• hand it over, subtract it, and repeat until nothing is owed.

Write share(loaves, people) that returns a tuple (whole, sizes): the number of whole loaves per customer and the list of the k values of the unit slices, in the order they are cut.

Examples

Input:  loaves = 3, people = 4
Output: (0, [2, 4])
Explanation: 3/4 = 1/2 + 1/4.

Input:  loaves = 4, people = 13
Output: (0, [4, 18, 468])
Explanation: 4/13 - 1/4 = 3/52, 3/52 - 1/18 = 1/468.

Input:  loaves = 7, people = 3
Output: (2, [3])

Constraints

• 0 <= loaves <= 10**6
• 1 <= people <= 200

Goals

• Represent a fraction exactly as a numerator and denominator
• Compute a ceiling with integer division only
• Keep a fraction in lowest terms inside a loop