<|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 `a = 1 and b = 1`, the graph is just a simple path. A path already has an Euler trail, so `extra = 0`.

---

### Case 2: Two-dimensional grid

If `a = 1 and b > 1`, the graph is a `b × c` rectangular 2D grid.

The optimal repeated edge count is `max(0, b + c - 5 + [b odd and c odd])`.

---

### Case 3: Genuine three-dimensional grid

Now assume `a >= 2`.

A vertex has odd degree iff an odd number of its coordinates are boundary coordinates. Thus odd vertices are face-interior vertices (exactly one boundary coordinate) and corners (exactly three boundary coordinates).

The face-interior bulk term is:

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

The remaining corner/parity correction is:

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

Therefore `extra = base + correction`.

---

### Final formula

```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 comments

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t x, y, z;

bool read() { return bool(cin >> x >> y >> z); }

void solve() {
    // We must walk every passageway of the X*Y*Z lattice graph at least once
    // and may start and finish at any two cabins, which is the open route
    // inspection (Chinese postman) problem. The answer is E, the number of
    // passageways, plus the fewest edges we are forced to repeat.
    //
    // A connected graph can be covered by a single walk that uses every edge
    // exactly once precisely when it has zero or two odd-degree vertices, and
    // when it has two they must be the walk's start and finish. We are allowed
    // to repeat edges, so the plan is to repeat just enough of them to drive
    // the count of odd-degree cabins down to two. Repeating every edge along a
    // path from u to v changes the degree parity only at the two ends u and v,
    // every interior vertex of the path gains two and stays the same parity. So
    // we can cancel the odd cabins by pairing them up and, for each pair,
    // repeating a shortest path between the two. The box is solid, so a
    // shortest path is just the Manhattan distance. Two odd cabins may be left
    // unpaired to serve as the endpoints, so the number of repeated edges we
    // add is the minimum weight perfect matching of the odd cabins with two of
    // them dropped.
    //
    // Which cabins are odd? Along an axis of size > 1, a coordinate at an end
    // (0 or size-1) has one neighbour on that axis while an interior coordinate
    // has two. A cabin's degree is therefore odd exactly when an odd number of
    // its coordinates are at an end: either one of them, which is a cabin
    // strictly inside one of the six faces, or all three, which is one of the
    // eight corners. A cabin with two end-coordinates lies on an edge of the
    // box and has even degree.
    //
    // The cabins strictly inside a single face all share the same fixed
    // end-coordinate and range over the interior values of the other two axes,
    // so they form a (p-2) x (q-2) grid in which lattice neighbours are one
    // step apart. We tile that grid with dominoes and repeat each domino's
    // single edge. The two faces of each orientation contribute (p-2)(q-2)
    // repeats, so summing the three orientations (a <= b <= c) gives D =
    // (a-2)(b-2) + (b-2)(c-2) + (a-2)(c-2). This is the bulk of the answer and
    // the part that scales with the box.
    //
    // The cabins a domino tiling can never place are the eight corners. A
    // corner's three neighbours all sit on box edges (two end-coordinates) and
    // have even degree, so a corner has no adjacent odd cabin to pair with. An
    // open walk gets two free odd-degree vertices though, namely its start and
    // finish, so we let two of the eight corners stay odd and use them as the
    // endpoints. That leaves 8 - 2 = 6 corners that still need repairing, which
    // pair up into 3 detours.
    //
    // Repairing a corner interacts with the tiling, which is the subtle part.
    // Picture one face whose interior is a 4 x 4 block: 16 cells, 8 dominoes,
    // no strays, with the face's 4 corners each sitting one diagonal step
    // (distance 2) off the block. Pairing those corners with one another is
    // costly because they are far apart. The cheaper move is to send each
    // corner 2 steps into the nearest block cell. That steals the 4
    // block-corner cells, yet the punctured 12-cell block still tiles, just
    // with 2 fewer dominoes. The four repairs therefore cost 4 x 2 for the
    // detours, offset by the 2 dominoes we no longer lay, for a net of only 6
    // above the bulk tiling, well below the 10 that pairing the corners
    // directly would run. The a-cases below are this same trade played out at
    // the scale of the real box.
    //
    // The cost of the three detours is a small constant set by the thinnest
    // dimension a and a couple of parities. The regimes below were worked out
    // by hand and then checked against a brute-force matching:
    //
    // - a = 2: the box is two cabins thick, so two corners on the same
    //          thin-axis edge are one step apart. Pair the six corners into
    //          three such adjacent pairs, one repeated edge each, for a total
    //          of 3.
    //
    // - a = 3: the box is three thick, so two corners now sit two steps apart
    //          along the thin axis. With b and c both even the six corners pair
    //          off that way for a total of 6. An odd b or c makes some faces
    //          have odd interior area, each leaving one stray cell that has to
    //          be picked up too, which raises the total to 7 for one odd
    //          dimension and to 9 for two.
    //
    // - a >= 4: corners are now too far apart to pair cheaply with one another,
    //           so each repaired corner instead steps one cabin into the
    //           nearest face, a detour of length 2. Repairing the six corners
    //           this way, with the odd faces' stray cells absorbed into those
    //           same detours, always nets out to 9 no matter how large the box
    //           grows.
    //
    // - a = 1: a flat sheet has no corners, and the pairing reduces to the
    //          planar value b + c - 5, plus one when b and c are both odd. A 1
    //          x 1 x c stick is a single path and needs no repeats at all.

    array<int64_t, 3> d = {x, y, z};
    sort(d.begin(), d.end());
    auto [a, b, c] = d;

    int64_t edges = (x - 1) * y * z + x * (y - 1) * z + x * y * (z - 1);

    int64_t extra;
    if(a == 1 && b == 1) {
        extra = 0;
    } else if(a == 1) {
        extra = max<int64_t>(0, b + c - 5 + (b % 2 == 1 && c % 2 == 1));
    } else {
        int64_t base =
            (a - 2) * (b - 2) + (b - 2) * (c - 2) + (a - 2) * (c - 2);
        int64_t correction;
        if(a == 2) {
            correction = 3;
        } else if(a == 3) {
            correction = array<int64_t, 3>{6, 7, 9}[b % 2 + c % 2];
        } else {
            correction = 9;
        }

        extra = base + correction;
    }

    cout << edges + extra << '\n';
}

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

    for(int test = 1; read(); test++) {
        cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with comments

```python
import sys


def solve_case(x, y, z):
    a, b, c = sorted((x, y, z))
    edges = (x - 1) * y * z + x * (y - 1) * z + x * y * (z - 1)

    if a == 1 and b == 1:
        extra = 0
    elif a == 1:
        both_odd = (b % 2 == 1 and c % 2 == 1)
        extra = max(0, b + c - 5 + int(both_odd))
    else:
        base = (a - 2) * (b - 2) + (a - 2) * (c - 2) + (b - 2) * (c - 2)
        if a == 2:
            correction = 3
        elif a == 3:
            parity_count = (b % 2) + (c % 2)
            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
    for i in range(0, len(data), 3):
        x, y, z = data[i], data[i + 1], data[i + 2]
        out.append(f"Case #{case_no}: {solve_case(x, y, z)}")
        case_no += 1
    sys.stdout.write("\n".join(out))


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