Water Jugs

Time limit2sMemory limit128 MB

Summary

Given three jug capacities with the third jug initially full, find all possible water amounts in the third jug when the first jug is empty, using pour-until-full-or-empty moves.

Level: Medium5 of 10
Topics: BFS, Simulation, Math
Solved: No attempts yet

Problem

There are three water jugs with capacities A, B, and C liters, where 1 <= A, B, C <= 200. At first, the first and second jugs are empty, and the third jug is full with C liters of water.

You may pour water from one jug into another. When pouring, you must continue until the source jug becomes empty or the destination jug becomes full. No water is lost during this process.

After repeating this process any number of times, find every amount of water that can be in the third jug in a state where the first jug is empty.

Input

The first line contains three integers A, B, and C separated by spaces.

Output

Print all possible amounts of water in the third jug in ascending order, separated by spaces.

Examples1

Example 1
Input
```
8 9 10
```
Expected output
```
1 2 8 9 10
```