Safe Deposit Business

Time limit1sMemory limit128 MB

Summary

Given grid points on a plane watched by two guards with line-of-sight blocked by intermediate lattice points, count vaults seen by zero, one, or both guards, using number theory (gcd/visibility) and careful counting over huge L.

Level: Hard8 of 10
Topics: Number theory, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

A company rents vaults arranged on a two-dimensional plane. Each vault is a point with integer coordinates. For every integer x with 1 <= x <= L and every integer y with -A <= y <= B, there is exactly one vault at (x, y), for a total of L * (A + B + 1) vaults.

Two guards watch the vaults. One guard stands at (0, -A), and the other stands at (0, B). A guard can see a vault if the open line segment between the guard and that vault contains no other vault.

A vault that neither guard can see is unsafe. A vault that exactly one guard can see is safe. A vault that both guards can see is very safe.

Given A, B, and L, count the unsafe, safe, and very safe vaults.

Input

The first line contains A and B. The second line contains L.

1 <= A, B <= 2000, 1 <= L <= 1,000,000,000.

Output

Print three lines. The first line must contain the number of unsafe vaults, the second line the number of safe vaults, and the third line the number of very safe vaults.

Examples3

Example 1
Input
```
1 1
3
```
Expected output
```
2
2
5
```
Example 2
Input
```
2 3
4
```
Expected output
```
0
16
8
```
Example 3
Input
```
7 11
1000000
```
Expected output
```
6723409
2301730
9974861
```