Description

In the Cartesian coordinate plane, there is a rectangle whose two opposite vertices on a diagonal are $(1,-A)$ and $(L,B)$. Inside this rectangle, there are $L \times (A+1+B)$ points.

Now there are two guards at the points $(0,-A)$ and $(0,B)$. They both look toward this rectangle. If a guard’s line of sight (a ray) to a point inside the rectangle is blocked by other points, then he cannot see that point.

For each point:

• If it can be seen by both guards, then it is considered very safe.
• If it can be seen by only one guard, then it is considered safe.
• If it cannot be seen by either guard, then it is considered dangerous.

Given $A$, $B$, and $L$, you need to find the numbers of very safe points, safe points, and dangerous points.

Input Format

The first line contains two integers $A$ and $B$.

The second line contains one integer $L$.

Output Format

Output $3$ lines. Each line contains one integer, in order: the number of dangerous points, the number of safe points, and the number of very safe points.

1 1
3

2
2
5

2 3
4

0
16
8

7 11
1000000

6723409
2301730
9974861

Hint

Constraints

• For $50\%$ of the testdata, $L \le 1000$.
• For another $25\%$ of the testdata, $A,B \le 100$.
• For $100\%$ of the testdata, $1 \le A,B \le 2000$, $1 \le L \le 10^9$.

Notes

This problem is translated from COCI2008-2009 CONTEST #4 T5 TREZOR.

Translated by ChatGPT 5