Three Bottle Juice Problem

Byteasar has three bottles of orange juice. The bottles have capacities A, B, and C liters respectively. Initially, the first and second bottles are empty and the third bottle is full, so the total amount of juice is C liters. Your task is to determine the minimum number of pouring operations required such that one of the bottles contains exactly k liters of juice, for each integer k from 0 to C.

The only allowed operation is to pour juice from one bottle to another. During a pouring operation, you must pour from one bottle to the other until either the source bottle becomes empty or the target bottle becomes full. Juice cannot be spilled and you cannot add any extra juice apart from what is already in the three bottles.

For example, if A = 1, B = 2, C = 3, then the initial state is (0, 0, 3). It is possible to achieve exactly 1 liter in one of the bottles with 1 pouring operation, and similarly, 2 liters can be measured in 1 operation, while 0 and 3 liters are already present in the initial state with 0 operations.

Determine for every k in the range [0, C] the minimum number of pours needed to have exactly k liters in some bottle, or output -1 if it is impossible.

Note: In each pouring operation, if you pour from bottle i to bottle j, you transfer \( d = \min(\text{current}[i], capacity_j - \text{current}[j]) \) liters from bottle i to bottle j. The state is represented as a triplet (amount in A, amount in B, amount in C).

inputFormat

The input consists of one line containing three integers A, B, and C (1 ≤ A, B, C ≤ 10^3), which represent the capacities of the three bottles. Initially, the bottles A and B are empty and bottle C is full.

outputFormat

For each integer k from 0 to C, print a line in the format:

k: number_of_operations

where number_of_operations is the minimum number of pouring operations required to have exactly k liters in one of the bottles, or -1 if it is impossible.

sample

1 2 3

0: 0
1: 1
2: 1
3: 0