<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

292. Field for the Cemetery
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



A new cemetery is going to be built in Petrozavodsk. It will look like qxc rectangle. You have to determine how many rectangular nx1 graves can be placed there. Graves may only be placed parallel to the sides of cemetery.


Input
There will be exactly three lines in the input, each containing one integer: q, c, and n (0 <= q,c <= 10^1000, 1 <= n <= 10^1000).

Output
Output a single number --- maximal number of graves.

Sample test(s)

Input
Test #1
4
5
3

Test #2
100000000000000000000000000000
100000000000000000000000000000
100000000000000000000000000001

Output
Test #1
6

Test #2
0
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

<|response|>
## 1. Abridged problem statement

Given a rectangle of size `q × c`, find the maximum number of axis-parallel graves of size `n × 1` that can fit inside it.

A grave may be placed either:

- horizontally: `1 × n`,
- vertically: `n × 1`.

The numbers `q`, `c`, and `n` can have up to `1000` decimal digits, so arbitrary-precision integers are required.

---

## 2. Key observations needed to solve the problem

### Observation 1: If one side is smaller than `n`

Suppose the rectangle sides are:

```text
short = min(q, c)
long  = max(q, c)
```

If:

```text
short < n
```

then a grave cannot be placed across the short side.

So all graves must be placed parallel to the long side.

Each of the `short` independent rows/columns can contain:

```text
floor(long / n)
```

graves.

Therefore:

```text
answer = short * floor(long / n)
```

This also gives `0` if both sides are smaller than `n`.

---

### Observation 2: If both sides are at least `n`

Assume:

```text
q >= n and c >= n
```

Write:

```text
q = x * n + s
c = y * n + t
```

where:

```text
s = q mod n
t = c mod n
0 <= s, t < n
```

The optimal answer is:

```text
answer = (q * c - s * t) / n + max(0, s + t - n)
```

Equivalently:

```text
answer = (q * c - min(s * t, (n - s) * (n - t))) / n
```

The first form is usually easier to implement.

---

### Observation 3: Why the formula is reasonable

If we tile only full `n`-blocks, the leftover corner of size `s × t` may remain unused, giving:

```text
(q * c - s * t) / n
```

graves.

However, when:

```text
s + t > n
```

a better “pinwheel” arrangement can save extra area and fit:

```text
s + t - n
```

additional graves.

So the final formula becomes:

```text
(q * c - s * t) / n + max(0, s + t - n)
```

---

## 3. Full solution approach based on the observations

We need only arithmetic with huge integers.

### Case 1: `q < n` or `c < n`

At least one side is too short for a grave in that direction.

Let:

```text
short = min(q, c)
long  = max(q, c)
```

Then only graves parallel to the long side can fit.

The answer is:

```text
short * (long / n)
```

where `/` is integer division.

---

### Case 2: `q >= n` and `c >= n`

Compute:

```text
s = q % n
t = c % n
```

The basic packing leaves an uncovered `s × t` corner, so it gives:

```text
(q * c - s * t) / n
```

graves.

If:

```text
s + t > n
```

then the pinwheel construction allows:

```text
s + t - n
```

extra graves.

Therefore:

```text
answer = (q * c - s * t) / n

if s + t > n:
    answer += s + t - n
```

---

### Correctness idea

Color every unit cell `(i, j)` by:

```text
(i + j) mod n
```

Every `n × 1` or `1 × n` grave covers exactly one cell of each color.

Therefore, the number of graves cannot exceed the number of cells of the least frequent color.

For `q = x * n + s` and `c = y * n + t`, counting the cells of each color gives the upper bound:

```text
(q * c - s * t) / n + max(0, s + t - n)
```

The described constructions achieve this bound:

- ordinary filling leaves `s * t` cells empty,
- pinwheel filling, when useful, leaves only `(n - s) * (n - t)` cells empty.

Thus the formula is optimal.

---

### Complexity

Let `D` be the number of decimal digits, up to `1000`.

The algorithm uses only a constant number of big integer operations.

```text
Time complexity:  polynomial in D
Memory complexity: O(D)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cpp_int q, c, n;

    // Read the dimensions of the cemetery and the grave length.
    cin >> q >> c >> n;

    cpp_int answer;

    // Case 1:
    // Both sides are at least n, so both orientations may be useful.
    if (q >= n && c >= n) {
        // Remainders after removing full blocks of size n.
        cpp_int s = q % n;
        cpp_int t = c % n;

        // Basic filling leaves an uncovered s * t corner.
        answer = (q * c - s * t) / n;

        // If s + t > n, the pinwheel construction fits extra graves.
        if (s + t > n) {
            answer += s + t - n;
        }
    }

    // Case 2:
    // At least one side is smaller than n.
    // Then graves can only be placed parallel to the longer side.
    else {
        cpp_int shortSide = (q < c ? q : c);
        cpp_int longSide = (q < c ? c : q);

        answer = shortSide * (longSide / n);
    }

    cout << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
# Python integers are arbitrary precision by default.

q = int(input())
c = int(input())
n = int(input())

# Case 1:
# Both sides are at least n, so we can use the optimal formula.
if q >= n and c >= n:
    # Leftover parts after taking full multiples of n.
    s = q % n
    t = c % n

    # Basic construction leaves an s * t corner uncovered.
    answer = (q * c - s * t) // n

    # Pinwheel improvement.
    if s + t > n:
        answer += s + t - n

# Case 2:
# One side is smaller than n, so only one orientation is possible.
else:
    short_side = min(q, c)
    long_side = max(q, c)

    # Each line along the short side contains floor(long_side / n) graves.
    answer = short_side * (long_side // n)

print(answer)
```