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

419. Hexagonal Walkaround
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A hexagonal leftist tank is a very complicated piece of machinery. It lives on a hexagonal grid, moving from a cell to some of its adjacent cells each turn.

More specifically, each moment of time the tank is located in some cell (x,y) of the grid, heading in one of six directions (see picture for the definition of coordinate system and directions). In one turn, the tank can either move forward in the direction it is heading, or turn left one direction (i.e., increase the direction it is heading by one modulo six), and then move forward in the new direction the tank is heading. Moreover, it is forbidden to move more than b times in the same direction consecutively.



You need to put the tank into cell (x,y), heading in direction d2, given it is located in cell (0,0) initially, heading in direction d1. What is the minimal number of turns required to do that?

Input
The input file contains five integer numbers x, y, d2, d1, b (-1012 ≤ x, y ≤ 1012, 0 ≤ d1, d2 ≤ 5, 2 ≤ b ≤ 10).

Output
Output one integer number — the minimal number of turns required to get the tank to the required position.

Example(s)
sample input
sample output
3 3 1 5 3
6

sample input
sample output
-1 -3 4 2 2
10



The second example is solved as follows (see next page):

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

A tank moves on a hexagonal grid. It starts at cell `(0, 0)` facing direction `d1`, and must reach cell `(x, y)` facing direction `d2`.

In one turn it must move one cell, and it can either:

- move forward in its current direction, or
- turn left by one direction modulo `6`, then move forward.

It is forbidden to move more than `b` times consecutively in the same direction.

Given `x, y, d2, d1, b`, find the minimum number of turns.

Coordinates can be as large as `10^12`, so direct graph search is impossible.

---

## 2. Key observations needed to solve the problem

### Observation 1: The path consists of consecutive direction runs

The tank can only keep its direction or increase it by `1 mod 6`.

Therefore, the sequence of used directions looks like:

```text
f, f, ..., f,
f+1, f+1, ...,
f+2, ...
```

modulo `6`.

So the path is made of **runs**. Each run uses one direction, and run directions are consecutive modulo `6`.

Each run length is between `1` and `b`.

---

### Observation 2: The first direction has only two choices

Initially the tank faces `d1`.

On the first turn, it can either:

1. move in direction `d1`,
2. turn left and move in direction `(d1 + 1) mod 6`.

So the first run direction `f` is either:

```text
d1
```

or

```text
(d1 + 1) mod 6
```

We can try both.

---

### Observation 3: For fixed first direction, the number of runs is fixed modulo 6

If the first run direction is `f`, and there are `R` runs, then the final run direction is:

```text
f + R - 1 mod 6
```

We need this to be `d2`.

Therefore:

```text
f + R - 1 ≡ d2 mod 6
```

The smallest positive such `R` is:

```text
R0 = ((d2 - f) mod 6) + 1
```

More generally:

```text
R = R0 + 6m
```

where `m >= 0` is the number of additional full cycles around all six directions.

---

### Observation 4: One move per run is forced

Each run has length at least `1`.

For a fixed `m`, direction `k` appears:

```text
m + c[k]
```

times, where `c[k]` is `1` if direction `k` appears in the initial `R0`-run fragment, otherwise `0`.

Thus, each direction has some forced moves, and some optional extra moves.

Each run can receive at most `b - 1` extra moves, so the capacity for extra moves in direction `k` is:

```text
cap[k] = (m + c[k]) * (b - 1)
```

---

### Observation 5: A full cycle of six directions has zero displacement

The six hex directions are:

```text
0: ( 1,  0)
1: ( 0,  1)
2: (-1,  1)
3: (-1,  0)
4: ( 0, -1)
5: ( 1, -1)
```

Their sum is zero.

So adding full cycles affects capacities, but the forced one-move-per-run displacement depends only on the initial `R0` fragment.

---

### Observation 6: Reduce movement to one variable

Pair opposite directions:

```text
axis 0: direction 0 vs direction 3
axis 1: direction 1 vs direction 4
axis 2: direction 2 vs direction 5
```

Let the extra moves create signed values:

```text
A = s[0] - s[3]
B = s[1] - s[4]
C = s[2] - s[5]
```

Direction `2` equals direction `1 - 0`, so the displacement from extras is:

```text
(A - C, B + C)
```

If the remaining displacement is `(Dx, Dy)`, then:

```text
A - C = Dx
B + C = Dy
```

Hence:

```text
A = Dx + C
B = Dy - C
```

Only `C` is free.

---

## 3. Full solution approach based on the observations

For each of the two possible first directions `f`:

### Step 1: Compute the base number of runs

```text
R0 = ((d2 - f) mod 6) + 1
```

Then total number of runs is:

```text
R = R0 + 6m
```

for some integer `m >= 0`.

---

### Step 2: Compute forced displacement

Let `c[k]` be how many times direction `k` appears in the first `R0` runs.

The forced displacement from one mandatory move in each base run is `(Cx, Cy)`.

Extra full cycles have zero net displacement, so they do not affect `(Cx, Cy)`.

The remaining displacement is:

```text
Dx = x - Cx
Dy = y - Cy
```

---

### Step 3: For fixed `m`, compute capacities

For direction `k`:

```text
cap[k] = (m + c[k]) * (b - 1)
```

This is the maximum number of extra moves possible in direction `k`.

---

### Step 4: Determine feasible interval for `C`

Recall:

```text
A = Dx + C
B = Dy - C
```

Capacity constraints:

```text
-cap[3] <= A <= cap[0]
-cap[4] <= B <= cap[1]
-cap[5] <= C <= cap[2]
```

Substitute `A` and `B`.

The valid interval for `C` is:

```text
lo = max(-cap[5], -cap[3] - Dx, Dy - cap[1])
hi = min( cap[2],  cap[0] - Dx, Dy + cap[4])
```

If:

```text
lo > hi
```

then this `m` is impossible.

---

### Step 5: Minimize extra moves for fixed `m`

For fixed `C`, the minimum number of extra moves is:

```text
|A| + |B| + |C|
```

Substitute:

```text
g(C) = |Dx + C| + |Dy - C| + |C|
```

This is a convex function.

Its unconstrained minimum is at the median of:

```text
-Dx, Dy, 0
```

Let that median be `Cstar`.

Because `C` must be inside `[lo, hi]`, the optimal value is:

```text
C = clamp(Cstar, lo, hi)
```

Then:

```text
extra = |Dx + C| + |Dy - C| + |C|
```

The total number of turns is:

```text
answer(m) = R0 + 6m + extra
```

---

### Step 6: Optimize over `m`

As `m` increases, capacities only increase, so feasibility is monotonic.

First, binary search the smallest feasible `m`.

Then, `answer(m)` is discrete convex / unimodal. Binary search the first `m` where:

```text
answer(m + 1) >= answer(m)
```

That gives the best `m` for this first direction.

Finally, take the minimum over the two possible first directions.

Special case:

```text
if x == 0 and y == 0 and d1 == d2:
    answer = 0
```

because no move is needed.

Complexity:

```text
O(log 10^12)
```

Memory:

```text
O(1)
```

---

## 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;
    int d2, d1, b;

    // Input order is: x y d2 d1 b
    cin >> x >> y >> d2 >> d1 >> b;

    // Hex-grid direction vectors.
    const int vx[6] = {1, 0, -1, -1, 0, 1};
    const int vy[6] = {0, 1, 1, 0, -1, -1};

    // Already at the target position and facing the target direction.
    if (x == 0 && y == 0 && d1 == d2) {
        cout << 0 << '\n';
        return 0;
    }

    // Large enough upper bound for the number of full direction cycles.
    const int64 MHI = 6000000000000LL;

    int64 answer = LLONG_MAX;

    // First move can either use d1 directly, or turn left first and use d1 + 1.
    for (int turn = 0; turn < 2; turn++) {
        int firstDir = (d1 + turn) % 6;

        // Minimal positive number of runs needed to end with direction d2.
        int R0 = ((d2 - firstDir + 6) % 6) + 1;

        // c[k] = how many times direction k appears in the initial R0 runs.
        int64 c[6] = {0, 0, 0, 0, 0, 0};

        for (int i = 0; i < R0; i++) {
            c[(firstDir + i) % 6]++;
        }

        // Forced displacement from one mandatory move in each base run.
        // Full six-direction cycles have zero displacement, so only c[k] matters.
        int64 Cx = 0;
        int64 Cy = 0;

        for (int k = 0; k < 6; k++) {
            Cx += c[k] * vx[k];
            Cy += c[k] * vy[k];
        }

        // Remaining displacement that must be produced by extra moves.
        int64 Dx = x - Cx;
        int64 Dy = y - Cy;

        // We minimize:
        // |Dx + C| + |Dy - C| + |C|
        //
        // This is minimized at median(-Dx, Dy, 0).
        vector<int64> vals = {-Dx, Dy, 0};
        sort(vals.begin(), vals.end());
        int64 Cstar = vals[1];

        // Capacity for extra moves in direction k with m full cycles.
        auto cap = [&](int64 m, int k) -> int64 {
            return (m + c[k]) * (b - 1);
        };

        // Evaluate a fixed m.
        //
        // Returns:
        //   first  = whether m is feasible
        //   second = minimal total number of turns if feasible
        auto evaluate = [&](int64 m) -> pair<bool, int64> {
            // Feasible interval for C.
            //
            // C itself is net movement on axis 2:
            //   -cap[5] <= C <= cap[2]
            //
            // A = Dx + C is net movement on axis 0:
            //   -cap[3] <= Dx + C <= cap[0]
            //
            // B = Dy - C is net movement on axis 1:
            //   -cap[4] <= Dy - C <= cap[1]

            int64 lo = max({
                -cap(m, 5),
                -cap(m, 3) - Dx,
                Dy - cap(m, 1)
            });

            int64 hi = min({
                cap(m, 2),
                cap(m, 0) - Dx,
                Dy + cap(m, 4)
            });

            // No valid C exists.
            if (lo > hi) {
                return {false, 0};
            }

            // Clamp the unconstrained optimum to the feasible interval.
            int64 C = max(lo, min(hi, Cstar));

            // Minimum number of extra moves.
            int64 extra = llabs(Dx + C) + llabs(Dy - C) + llabs(C);

            // Forced moves: one per run.
            // Total runs = R0 + 6m.
            int64 total = R0 + 6 * m + extra;

            return {true, total};
        };

        // Binary search the first feasible m.
        // Feasibility is monotonic because capacities only grow with m.
        int64 lo = 0;
        int64 hi = MHI;

        while (lo < hi) {
            int64 mid = lo + (hi - lo) / 2;

            if (evaluate(mid).first) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        int64 firstFeasible = lo;

        // Now minimize answer(m), which is unimodal / discrete convex.
        lo = firstFeasible;
        hi = MHI;

        while (lo < hi) {
            int64 mid = lo + (hi - lo) / 2;

            int64 cur = evaluate(mid).second;
            int64 nxt = evaluate(mid + 1).second;

            // If moving to mid + 1 does not improve the answer,
            // the optimum is at mid or to the left.
            if (nxt >= cur) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        answer = min(answer, evaluate(lo).second);
    }

    cout << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    # Input order is: x y d2 d1 b
    x, y, d2, d1, b = map(int, sys.stdin.read().split())

    # Hex-grid direction vectors.
    vx = [1, 0, -1, -1, 0, 1]
    vy = [0, 1, 1, 0, -1, -1]

    # Already at the target position and facing the target direction.
    if x == 0 and y == 0 and d1 == d2:
        print(0)
        return

    # Large enough upper bound for the number of full direction cycles.
    MHI = 6_000_000_000_000

    best = None

    # First move can either use d1 directly, or turn left first and use d1 + 1.
    for turn in range(2):
        first_dir = (d1 + turn) % 6

        # Minimal positive number of runs needed to end with direction d2.
        R0 = ((d2 - first_dir) % 6) + 1

        # c[k] = how many times direction k appears in the initial R0 runs.
        c = [0] * 6

        for i in range(R0):
            c[(first_dir + i) % 6] += 1

        # Forced displacement from one mandatory move in each base run.
        # Full six-direction cycles have zero displacement, so only c[k] matters.
        Cx = 0
        Cy = 0

        for k in range(6):
            Cx += c[k] * vx[k]
            Cy += c[k] * vy[k]

        # Remaining displacement that must be produced by extra moves.
        Dx = x - Cx
        Dy = y - Cy

        # We minimize:
        # |Dx + C| + |Dy - C| + |C|
        #
        # This is minimized at median(-Dx, Dy, 0).
        vals = [-Dx, Dy, 0]
        vals.sort()
        Cstar = vals[1]

        def cap(m, k):
            """
            Maximum number of extra moves in direction k.

            Direction k appears m + c[k] times as a run.
            Each run can receive at most b - 1 extra moves.
            """
            return (m + c[k]) * (b - 1)

        def evaluate(m):
            """
            Evaluate a fixed number m of full six-direction cycles.

            Returns:
                feasible: whether this m can reach the target
                total: minimal number of turns if feasible
            """

            # Let C be net extra movement on axis 2:
            #   C = s[2] - s[5]
            #
            # Then:
            #   A = Dx + C = s[0] - s[3]
            #   B = Dy - C = s[1] - s[4]
            #
            # Apply capacities to all three axes.

            lo = max(
                -cap(m, 5),          # -cap[5] <= C
                -cap(m, 3) - Dx,     # -cap[3] <= Dx + C
                Dy - cap(m, 1),      # Dy - C <= cap[1]
            )

            hi = min(
                cap(m, 2),           # C <= cap[2]
                cap(m, 0) - Dx,      # Dx + C <= cap[0]
                Dy + cap(m, 4),      # -cap[4] <= Dy - C
            )

            # No valid C exists.
            if lo > hi:
                return False, 0

            # Clamp the unconstrained optimum to the feasible interval.
            C = max(lo, min(hi, Cstar))

            # Minimum number of extra moves.
            extra = abs(Dx + C) + abs(Dy - C) + abs(C)

            # Forced moves: one per run.
            # Total runs = R0 + 6m.
            total = R0 + 6 * m + extra

            return True, total

        # Binary search the first feasible m.
        # Feasibility is monotonic because capacities only grow with m.
        lo = 0
        hi = MHI

        while lo < hi:
            mid = (lo + hi) // 2

            feasible, _ = evaluate(mid)

            if feasible:
                hi = mid
            else:
                lo = mid + 1

        first_feasible = lo

        # Now minimize answer(m), which is unimodal / discrete convex.
        lo = first_feasible
        hi = MHI

        while lo < hi:
            mid = (lo + hi) // 2

            _, cur = evaluate(mid)
            _, nxt = evaluate(mid + 1)

            # If moving to mid + 1 does not improve the answer,
            # the optimum is at mid or to the left.
            if nxt >= cur:
                hi = mid
            else:
                lo = mid + 1

        _, candidate = evaluate(lo)

        if best is None or candidate < best:
            best = candidate

    print(best)


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