<|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.

470. The Death Cube
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A long time ago, in a Galaxy Far Far Again...



New dangerous mission undertake Jedi Knights. Latest and most powerful weapon of the Empire — the Death Cube — decided they to destroy. Not easy the mission is — new modified battle droids withstand them to, and very complex and awkward structure the Death Cube has. Specifically, many tiers consists the Cube of, and cellular structure each tier has. It is unimportant which face of the cube start you to mark out tiers from — every time distinguish tiers will you be able to. X tiers in one dimension of the Cube could count you, Y tiers in the second dimension, and Z tiers in the third one. Thus, not cube the Death Cube is, but rectangular parallelepiped instead, and XYZ cabins has the Cube. In other words, in a 3-D space can be allocated the Cube so that in integer point the center of every cabin is, and every integer point inside the Cube is the center of a cabin. In this system between any two cabins passageway exists if and only if exactly one unit the distance between the cabins is. For you convenience, to you example of the Cube with X=Y=Z=2 is given.

The Cube to destroy, plan to place a bomb in every passageway of the Cube Jedi Knights. So to do, should in some cabin close to the outer surface of the Cube start the mission detachment of Jedis to. From cabin to cabin by moving, should mine they passageways passed, and in one of the cabins close to the outer surface of the Cube should finish their mission Jedi Knights. During their trip cannot separate from each other Jedis — only all together can overpower battle droids they. That what your job is — find the shortest way which should overpass Jedis to.

Input
Several descriptions of Death Cubes input file may contain (since indefatigable the Emperor is, and construct new Cubes continues he to). Only three numbers — X, Y and Z — contains every line of input ().

Output
For every Cube, only length of the shortest way should output you, and the way itself will help to Jedis the Power find to. Output details in example will find you.

Example(s)
sample input
sample output
2 1 2
2 2 2
Case #1: 4
Case #2: 15



The following way one of the possible solutions to the Cube from the second example (and from the picture) is: 1—2—3—4—1—5—6—2—3—7—6—5—8—4—8—7.

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

We are given a rectangular 3D grid of cabins of size `X × Y × Z`.

Two cabins are connected by a passageway if they differ by exactly `1` in one coordinate and are equal in the other two coordinates.

The Jedis must walk through the grid and place a bomb in every passageway. They may traverse a passageway more than once. They must start and finish in cabins on the outer surface.

For every input line `X Y Z`, output the minimum possible walk length.

Output format:

```text
Case #k: answer
```

---

## 2. Key observations needed to solve the problem

### Observation 1: This is an open Chinese Postman Problem

Model the Death Cube as an undirected graph:

- cabins are vertices,
- passageways are edges.

We need the shortest walk that visits every edge at least once.

If every edge were used exactly once, the walk would be an Euler trail.

For an undirected connected graph:

- Euler circuit exists if there are `0` odd-degree vertices.
- Euler path exists if there are exactly `2` odd-degree vertices.

If there are more odd-degree vertices, we must repeat some edges.

---

### Observation 2: Answer = number of edges + minimum repeated edges

Every passageway must be used at least once.

The number of original edges is:

```text
E = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

The only remaining task is to compute the minimum number of extra repeated edges.

---

### Observation 3: Repeating a path fixes parity of its endpoints

If we repeat all edges along a path from vertex `u` to vertex `v`, then:

- degree parity of `u` changes,
- degree parity of `v` changes,
- all internal vertices change by `2`, so their parity does not change.

Therefore, odd-degree vertices must be paired by repeated paths.

Because the walk may be open, we may leave two odd vertices unpaired: they become the start and finish.

In a grid graph, shortest path distance is Manhattan distance.

---

### Observation 4: Sort the dimensions

The formula depends only on the side lengths, not on their order.

Let:

```text
a <= b <= c
```

be the sorted values of `X, Y, Z`.

---

## 3. Full solution approach based on the observations

First compute:

```text
edges = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

Then compute `extra`, the minimum number of repeated edges.

The final answer is:

```text
answer = edges + extra
```

---

### Case 1: One-dimensional graph

If:

```text
a = 1 and b = 1
```

then the graph is just a simple path of length `c - 1`.

A path already has an Euler trail, so:

```text
extra = 0
```

---

### Case 2: Two-dimensional grid

If:

```text
a = 1 and b > 1
```

then the graph is a `b × c` rectangular 2D grid.

The optimal repeated edge count is:

```text
extra = b + c - 5
```

If both `b` and `c` are odd, one more repeated edge is needed:

```text
extra = b + c - 5 + 1
```

For very small grids, this value can become negative, so we clamp it to zero:

```text
extra = max(0, b + c - 5 + [b odd and c odd])
```

---

### Case 3: Genuine three-dimensional grid

Now assume:

```text
a >= 2
```

A vertex degree depends on how many of its coordinates lie on the boundary.

For each coordinate:

- boundary coordinate contributes `1` neighbor in that direction,
- interior coordinate contributes `2` neighbors in that direction.

So a vertex has odd degree iff an odd number of its coordinates are boundary coordinates.

Thus odd vertices are:

1. face-interior vertices, with exactly one boundary coordinate,
2. corners, with exactly three boundary coordinates.

Vertices on edges of the box but not corners have exactly two boundary coordinates, so they have even degree.

---

### Bulk contribution from face interiors

For a pair of opposite faces of size `p × q`, the strict face interior has size:

```text
(p - 2) × (q - 2)
```

The face-interior odd vertices can mostly be paired by neighboring dominoes of cost `1`.

Summing over the three face orientations gives the bulk term:

```text
base =
    (a - 2)(b - 2)
  + (a - 2)(c - 2)
  + (b - 2)(c - 2)
```

The remaining issue is caused by corners and parity leftovers on faces.

This produces a small correction depending on the smallest dimension.

---

### Boundary correction

If `a = 2`:

```text
correction = 3
```

If `a = 3`, the correction depends on the parity of `b` and `c`:

```text
number of odd values among b and c = 0 -> correction = 6
number of odd values among b and c = 1 -> correction = 7
number of odd values among b and c = 2 -> correction = 9
```

So:

```text
correction = [6, 7, 9][(b % 2) + (c % 2)]
```

If `a >= 4`:

```text
correction = 9
```

Therefore, for the 3D case:

```text
extra = base + correction
```

---

### Final formula

Sort dimensions:

```text
a <= b <= c
```

Compute:

```text
edges = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

Then:

```text
if a == 1 and b == 1:
    extra = 0
elif a == 1:
    extra = max(0, b + c - 5 + [b odd and c odd])
else:
    base =
        (a - 2)(b - 2)
      + (a - 2)(c - 2)
      + (b - 2)(c - 2)

    if a == 2:
        correction = 3
    elif a == 3:
        correction = [6, 7, 9][(b % 2) + (c % 2)]
    else:
        correction = 9

    extra = base + correction

answer = edges + extra
```

Each test case is solved in `O(1)` time.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

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

    int64 x, y, z;
    int caseNo = 1;

    // Input contains an unknown number of test cases, one per line.
    while (cin >> x >> y >> z) {
        // Sort dimensions because the formula depends only on side lengths,
        // not on which side is called X, Y, or Z.
        array<int64, 3> d = {x, y, z};
        sort(d.begin(), d.end());

        int64 a = d[0];
        int64 b = d[1];
        int64 c = d[2];

        // Count all original passageways.
        //
        // Edges parallel to X-axis:
        //   (x - 1) * y * z
        //
        // Edges parallel to Y-axis:
        //   x * (y - 1) * z
        //
        // Edges parallel to Z-axis:
        //   x * y * (z - 1)
        int64 edges =
            (x - 1) * y * z +
            x * (y - 1) * z +
            x * y * (z - 1);

        int64 extra = 0;

        if (a == 1 && b == 1) {
            // The graph is a simple path.
            // A path can be traversed from one end to the other without
            // repeating any edge.
            extra = 0;
        } else if (a == 1) {
            // The graph is a 2D b by c rectangular grid.
            //
            // Minimum repeated edges:
            //   b + c - 5
            //
            // If both dimensions are odd, one additional repeated edge is needed.
            //
            // For tiny grids like 2x2, the expression may become negative,
            // so clamp it to 0.
            int64 bothOdd = (b % 2 == 1 && c % 2 == 1) ? 1 : 0;
            extra = max<int64>(0, b + c - 5 + bothOdd);
        } else {
            // Genuine 3D grid: all dimensions are at least 2.

            // Bulk repeated-edge contribution from pairing odd vertices
            // inside faces.
            int64 base =
                (a - 2) * (b - 2) +
                (a - 2) * (c - 2) +
                (b - 2) * (c - 2);

            // Small boundary correction caused by corners and parity leftovers.
            int64 correction;

            if (a == 2) {
                correction = 3;
            } else if (a == 3) {
                // Number of odd dimensions among b and c.
                //
                // 0 -> both even, correction 6
                // 1 -> one odd,   correction 7
                // 2 -> both odd,  correction 9
                int parityCount = (b % 2) + (c % 2);

                int64 table[3] = {6, 7, 9};
                correction = table[parityCount];
            } else {
                correction = 9;
            }

            extra = base + correction;
        }

        int64 answer = edges + extra;

        cout << "Case #" << caseNo << ": " << answer << '\n';

        caseNo++;
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve_case(x, y, z):
    """
    Return the minimum walk length needed to traverse every passageway
    in an x by y by z rectangular grid graph.
    """

    # Sort dimensions because the formula is symmetric.
    a, b, c = sorted((x, y, z))

    # Count original passageways.
    #
    # Along X direction:
    #   (x - 1) * y * z
    #
    # Along Y direction:
    #   x * (y - 1) * z
    #
    # Along Z direction:
    #   x * y * (z - 1)
    edges = (
        (x - 1) * y * z
        + x * (y - 1) * z
        + x * y * (z - 1)
    )

    # Compute minimum number of repeated edges.
    if a == 1 and b == 1:
        # One-dimensional path.
        # No edge has to be repeated.
        extra = 0

    elif a == 1:
        # Two-dimensional b by c grid.
        #
        # Formula:
        #   b + c - 5
        #
        # Add 1 if both b and c are odd.
        # Clamp to 0 for very small grids.
        both_odd = (b % 2 == 1 and c % 2 == 1)
        extra = max(0, b + c - 5 + int(both_odd))

    else:
        # Genuine 3D case.

        # Bulk contribution from pairing face-interior odd vertices.
        base = (
            (a - 2) * (b - 2)
            + (a - 2) * (c - 2)
            + (b - 2) * (c - 2)
        )

        # Boundary correction from corners and parity leftovers.
        if a == 2:
            correction = 3
        elif a == 3:
            # Number of odd dimensions among b and c.
            parity_count = (b % 2) + (c % 2)

            # parity_count = 0 -> correction 6
            # parity_count = 1 -> correction 7
            # parity_count = 2 -> correction 9
            correction = [6, 7, 9][parity_count]
        else:
            correction = 9

        extra = base + correction

    return edges + extra


def main():
    data = list(map(int, sys.stdin.read().split()))

    out = []
    case_no = 1

    # Every test case consists of exactly three integers.
    for i in range(0, len(data), 3):
        x, y, z = data[i], data[i + 1], data[i + 2]

        answer = solve_case(x, y, z)

        out.append(f"Case #{case_no}: {answer}")
        case_no += 1

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()
```