## 1. Abridged problem statement

Given a `q × c` rectangular field, find the maximum number of `n × 1` rectangular graves that can be placed inside it. Graves must be axis-parallel, so each grave is either horizontal or vertical.

Input contains exactly three integers `q`, `c`, `n`, each possibly extremely large:

- `0 ≤ q, c ≤ 10^1000`
- `1 ≤ n ≤ 10^1000`

Output the maximum number of graves.

---

## 2. Detailed editorial

We need maximize the number of axis-parallel `n × 1` strips packed into a `q × c` rectangle.

Because the numbers have up to `1000` decimal digits, the main challenge is not complexity but deriving a formula that only needs big integer arithmetic.

---

### Case 1: One side is smaller than `n`

If `min(q, c) < n`, then a grave cannot be placed along the short side.

So every grave must be parallel to the longer side.

If the rectangle has dimensions:

```text
short × long
```

then each of the `short` rows/columns can contain:

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

graves.

Therefore:

```text
answer = min(q, c) * floor(max(q, c) / n)
```

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

---

### Case 2: 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 answer is:

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

Equivalently, since each grave covers `n` cells:

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

where:

```text
deficiency = min(s * t, (n - s) * (n - t))
```

---

### Why is this an upper bound?

Color the infinite grid using `n` colors:

```text
color(i, j) = (i + j) mod n
```

Any horizontal or vertical `n × 1` grave covers `n` consecutive cells, so it contains exactly one cell of each color.

Therefore, if there are `T` graves, then for every color `k`:

```text
T ≤ number of cells of color k inside the q × c rectangle
```

So:

```text
T ≤ minimum color-class size
```

Now count the number of cells of each color.

Let:

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

Rows of each residue modulo `n` appear either `x` or `x + 1` times. Exactly `s` row residues appear `x + 1` times.

Similarly, columns of each residue appear either `y` or `y + 1` times. Exactly `t` column residues appear `y + 1` times.

For any color `k`, its count has a common base part:

```text
n * x * y + x * t + y * s
```

plus an extra term `Q_k`, which counts overlaps between two cyclic intervals of lengths `s` and `t`.

The minimum possible overlap of two cyclic arcs of lengths `s` and `t` on a cycle of length `n` is:

```text
max(0, s + t - n)
```

Therefore:

```text
T ≤ n*x*y + x*t + y*s + max(0, s + t - n)
```

This simplifies to:

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

---

### Why is this bound achievable?

When both `q ≥ n` and `c ≥ n`, we can construct a packing matching the bound.

First tile the large full multiples of `n`.

Write:

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

Because `x, y ≥ 1`, remove and completely tile:

1. The top `(x - 1) * n` rows using vertical graves.
2. From the remaining rectangle, the left `(y - 1) * n` columns using horizontal graves.

This leaves only a smaller corner rectangle:

```text
(n + s) × (n + t)
```

Now we need optimally fill this corner.

There are two natural fillings.

---

#### Simple filling

Fill:

- one horizontal grave in each row, covering `n` cells;
- one vertical grave in each remaining extra column.

This leaves an empty `s × t` corner.

Deficiency:

```text
s * t
```

---

#### Pinwheel filling

If `s + t > n`, we can do better by arranging four arms in a pinwheel pattern.

The empty hole then has size:

```text
(n - s) × (n - t)
```

Deficiency:

```text
(n - s) * (n - t)
```

This is better exactly when:

```text
(n - s) * (n - t) < s * t
```

which simplifies to:

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

So the optimal deficiency is:

```text
min(s * t, (n - s) * (n - t))
```

Thus the maximum number of graves is:

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

which is the same as:

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

---

## 3. Commented C++ solution

The original submitted file contains a custom `bigint` implementation because C++ has no built-in arbitrary-precision integer type. The actual algorithm is very short.

Below is the same solution written with `boost::multiprecision::cpp_int`, with detailed comments. It computes exactly the same formula as the provided solution.

```cpp
#include <bits/stdc++.h>                  // Include most standard C++ headers.
#include <boost/multiprecision/cpp_int.hpp> // Include arbitrary-precision integer type.

using namespace std;                       // Use standard namespace.
using boost::multiprecision::cpp_int;       // Use cpp_int as big integer type.

int main() {
    ios::sync_with_stdio(false);            // Speed up C++ input/output.
    cin.tie(nullptr);                       // Untie cin from cout for faster input.

    cpp_int q, c, n;                        // Field dimensions q, c and grave length n.

    cin >> q >> c >> n;                     // Read the three huge integers.

    cpp_int ans;                            // This will store the final answer.

    // If both sides are at least n, both horizontal and vertical graves can be useful.
    if (q >= n && c >= n) {
        cpp_int s = q % n;                  // Remaining rows after taking full blocks of size n.
        cpp_int t = c % n;                  // Remaining columns after taking full blocks of size n.

        // Basic filling leaves an s * t corner uncovered.
        // Since every grave covers n cells, this gives (q*c - s*t) / n graves.
        ans = (q * c - s * t) / n;

        // If s + t > n, a pinwheel arrangement saves extra uncovered area.
        // It improves the number of graves by exactly s + t - n.
        if (s + t > n) {
            ans += s + t - n;               // Add the pinwheel bonus.
        }
    } else {
        // If one side is smaller than n, graves can only be placed along the longer side.

        cpp_int mn = (q < c ? q : c);        // The shorter side.
        cpp_int mx = (q < c ? c : q);        // The longer side.

        // Each of mn lines can contain floor(mx / n) graves.
        ans = mn * (mx / n);
    }

    cout << ans << '\n';                    // Print the maximum number of graves.

    return 0;                               // Finish successfully.
}
```

If keeping the original custom `bigint` file, the important part is exactly this logic:

```cpp
bigint ans;

if (q >= n && c >= n) {
    bigint s = q % n;
    bigint t = c % n;

    ans = (q * c - s * t) / n;

    if (s + t > n) {
        ans += s + t - n;
    }
} else {
    ans = min(q, c) * (max(q, c) / n);
}
```

Everything before that in the original file implements arbitrary-precision arithmetic: addition, subtraction, multiplication, division, modulo, comparison, and input/output for huge integers.

---

## 4. Python solution with detailed comments

Python integers are arbitrary precision by default, so the implementation is very short.

```python
# Read q: one side of the cemetery rectangle.
q = int(input())

# Read c: the other side of the cemetery rectangle.
c = int(input())

# Read n: grave length, each grave has size n x 1.
n = int(input())

# If both sides are at least n, we can use the full optimal formula.
if q >= n and c >= n:
    # s is the leftover part of q after full blocks of length n.
    s = q % n

    # t is the leftover part of c after full blocks of length n.
    t = c % n

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

    # If s + t > n, the pinwheel construction improves the packing.
    if s + t > n:
        ans += s + t - n

# Otherwise, one side is too short to fit a grave across it.
else:
    # The shorter side gives the number of independent rows/columns.
    short = min(q, c)

    # The longer side is where graves are placed.
    long = max(q, c)

    # Each of the short lines contains floor(long / n) graves.
    ans = short * (long // n)

# Output the maximum possible number of graves.
print(ans)
```

---

## 5. Compressed editorial

Let the rectangle be `q × c`, grave size `n × 1`.

If `min(q, c) < n`, only one orientation is possible, so:

```text
answer = min(q, c) * floor(max(q, c) / n)
```

Otherwise, write:

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

with `0 ≤ s,t < n`.

Color cell `(i,j)` by `(i+j) mod n`. Every grave covers exactly one cell of each color, so the number of graves is at most the smallest color class. Counting color classes gives:

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

This bound is achievable. Tile all full `n`-multiple slabs, leaving a corner of size:

```text
(n+s) × (n+t)
```

This corner can be filled leaving either:

```text
s*t
```

cells empty, or, using a pinwheel construction when `s+t > n`:

```text
(n-s)*(n-t)
```

cells empty.

Thus the optimal formula for `q,c ≥ n` is:

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

Use arbitrary-precision integers because inputs have up to `1000` digits.