## 1) Abridged problem statement

You have an \(H \times W\) grid. A cop and a thief start in different cells. They move alternately; each move must go to a side-adjacent cell (up/down/left/right). Staying in place is not allowed, and moving outside the grid is not allowed.

The cop wants to catch the thief as soon as possible; the thief wants to avoid being caught (or delay it as much as possible). Both play optimally and have full information.

If the cop can guarantee catching the thief, output the move number on which the capture occurs (moves are numbered globally starting from 1). Otherwise output `0`.

Constraints: \(1 \le H,W \le 5\cdot 10^8\).

---

## 2) Detailed Editorial

### Key observations

This game is on a grid graph. Two major phenomena decide the outcome:

1. **1D case (a line):**
   If \(H=1\) or \(W=1\), the grid is a path. Since players must move every turn, parity matters and eventually the cop catches the thief (there is no way to "dance forever" without being forced into a meeting), but the exact time depends on positions and parity.

2. **2D case (both dimensions > 1): bipartite coloring (chessboard parity):**
   Color cell \((r,c)\) by parity of \(r+c\) (like a chessboard). Every move flips the color (because you change exactly one coordinate by 1).

   If the two players start on **different colors**, then the thief can always pick a free cell of the cop's current colour, so the chase never converges:
   - When both dimensions > 1 and initial colors differ, the thief can avoid capture forever ⇒ answer `0`.

3. **Otherwise (same color, both dimensions > 1):**
   The cop can force capture. The thief's best defense is to run toward a corner; intuitively corners minimize escape options and force a "squeeze".

The provided solution does not simulate (impossible for huge \(H,W\)); it computes the capture time in **closed form**, after reducing to canonical orientation.

---

### Canonical transformations used by the code

Let cop be \(C=(x_c,y_c)\), thief \(T=(x_t,y_t)\).

The code performs symmetry reductions so it can assume a standard case:

1. **Ensure vertical distance dominates:**
   If \(|x_c-x_t| < |y_c-y_t|\), it swaps x with y for both players and also swaps \(H\) with \(W\).
   So afterward: \(|x_c-x_t| \ge |y_c-y_t|\).
   This means "the main separation is in the x/row direction".

2. **Ensure cop is "above" thief in x:**
   If \(x_c > x_t\), it reflects vertically: map \(x \mapsto (H+1-x)\).
   After this, \(x_c \le x_t\).

These preserve game outcome and capture time, just expressed in a normalized coordinate frame.

---

### Accounting for who moves first

The solution then converts to a simpler "thief moves first" style:

- If the first mover is `"C"`, the code **executes one cop move immediately**: it increments \(x_c\) by 1 and increments `ans` by 1.
  This corresponds to "cop uses his first move to close the dominant x-gap" (the optimal move under the normalization).

If after that move positions coincide, capture happens immediately at move `ans`.

---

### Case A: 1D grid (after normalization this appears as `m == 1`)

After possible swapping, `m` is the width. If `m==1`, the grid is a single column of height `n`.

The code outputs:
```text
ans += (n - x_c - 1) * 2;
ans += ((x_c ^ x_t) & 1);
```

Interpretation:

- The cop will chase toward the far end (bottom) while the thief is forced to bounce; with mandatory movement, the game length is basically "how many forced steps until the cop reaches the end region" times 2 (because moves alternate).
- The final parity tweak `((x_c ^ x_t) & 1)` adjusts whether an extra move is needed depending on whether they are on opposite parity positions along the line (since each move flips parity along the path).

Thus capture is guaranteed; compute exact move count.

---

### Case B: both dimensions > 1 and opposite colors ⇒ infinite evasion

The code checks:
```text
if ( ((x_c ^ y_c) ^ (x_t ^ y_t)) & 1 ) cout << 0;
```
Because parity of \(x+y\) mod 2 equals the LSB of \(x \oplus y\), this condition tests whether \((x_c+y_c)\) and \((x_t+y_t)\) differ mod 2.

If different ⇒ output `0`.

---

### Case C: same color, both dimensions > 1 ⇒ capture time formula

Now capture is forced. The code splits into two geometric subcases based on whether the two positions lie on a 45° diagonal:

#### C1) Equal absolute differences: \(|x_c-x_t| = |y_c-y_t|\)

This means they are on a diagonal line where an optimal "mirroring" defense changes; the formula differs.

The code first ensures \(y_c \ge y_t\) by reflecting horizontally if needed (`y -> m+1-y`), then:
```text
ans += (y_c - x_c + n - 2) * 2;
```

This corresponds to: time until the cop can "line up" and then force capture while the thief runs to the corner consistent with that diagonal configuration. The expression is essentially the distance (in a transformed coordinate system) to a decisive boundary, multiplied by 2 for alternating moves.

#### C2) Otherwise: not on a diagonal

Then:
```text
ans += (n - x_c - 1 + max(y_c - 1, m - y_c)) * 2;
```

Interpretation:
- `n - x_c - 1` = how far the cop is from the bottom border (in x).
- `max(y_c - 1, m - y_c)` = distance from cop to the farther horizontal border (left or right).
- Sum = distance to a "most constraining corner region" that ensures eventual capture under optimal play.
- Multiply by 2 because players alternate moves.

This matches the strategy: the thief runs to a corner; the cop reduces the region.

---

### Complexity

All operations are O(1), just arithmetic, suitable for huge \(H,W\).

---

## 3) C++ Solution

```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;
};

int n, m;
pair<int, int> p_cop, p_thief;
string first_mover;

void read() {
    cin >> n >> m;
    cin >> p_cop >> p_thief;
    cin >> first_mover;
}

void solve() {
    // This is a direct constructive problem with analyzing the cases. WLOG, we
    // will assume that the distance by x is greater or equal than the distance
    // by y. And similarly we can assume cop_x <= thief_x. If the cop moves
    // first, it would make sense to close down the larger distance (or the one
    // on x). Now we can assume that the thief moves first. There are a few
    // cases:
    //
    //     1) Corner case of m = 1 or n = 1. Then the thief will immediately go
    //        to the border and the cop will eventually catch him. Depending on
    //        the parity, we might have to make one extra move as they can't
    //        stop moving.
    //
    //     2) Let's make a chess board. If neither of n or m is 1, and they
    //        start at different colours, the thief can always choose a cell
    //        that isn't occupied by the cop and is the same colour as the cop's
    //        current cell. Therefore, the game can continue indefinitely.
    //
    //     3) In all other cases, the cop can eventually get to a state where
    //        he catches the thief. We can notice that the optimal strategy of
    //        the thief is to go to one of the corners.
    //
    // A naive way is to try all 4 possible corners, but it's also not very
    // complicated to get the explicit closed form of the answer.

    if(abs(p_cop.first - p_thief.first) < abs(p_cop.second - p_thief.second)) {
        swap(p_cop.first, p_cop.second);
        swap(p_thief.first, p_thief.second);
        swap(n, m);
    }

    if(p_cop.first > p_thief.first) {
        p_cop.first *= -1;
        p_thief.first *= -1;
        p_cop.first += n + 1;
        p_thief.first += n + 1;
    }

    int ans = 0;
    if(first_mover == "C") {
        p_cop.first++;
        ans++;
    }

    if(p_cop == p_thief) {
        cout << ans << endl;
        return;
    }

    if(m == 1) {
        ans += (n - p_cop.first - 1) * 2;
        ans += (p_cop.first ^ p_thief.first) & 1;
        cout << ans << endl;
        return;
    }

    if(((p_cop.first ^ p_cop.second) ^ (p_thief.first ^ p_thief.second)) & 1) {
        cout << 0 << endl;
        return;
    }

    if(abs(p_cop.first - p_thief.first) == abs(p_cop.second - p_thief.second)) {
        if(p_cop.second < p_thief.second) {
            p_cop.second *= -1;
            p_thief.second *= -1;
            p_cop.second += m + 1;
            p_thief.second += m + 1;
        }
        ans += (p_cop.second - p_cop.first + n - 2) * 2;
        cout << ans << endl;
        return;
    }

    ans += (n - p_cop.first - 1 + max(p_cop.second - 1, m - p_cop.second)) * 2;
    cout << ans << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same logic)

```python
import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    # Read grid size
    n = int(next(it))   # height
    m = int(next(it))   # width

    # Read positions (row, col)
    cx = int(next(it)); cy = int(next(it))
    tx = int(next(it)); ty = int(next(it))

    first = next(it)    # 'C' or 'T'

    # --- Symmetry reduction 1: ensure |dx| >= |dy| by swapping axes if needed ---
    if abs(cx - tx) < abs(cy - ty):
        # swap x<->y for both players
        cx, cy = cy, cx
        tx, ty = ty, tx
        # swap dimensions accordingly
        n, m = m, n

    # --- Symmetry reduction 2: ensure cop is not below thief (cx <= tx) ---
    if cx > tx:
        # reflect vertically: x -> n+1-x
        cx = (n + 1) - cx
        tx = (n + 1) - tx

    ans = 0

    # If cop moves first, the solution assumes optimal is to move +1 in x direction
    # (downwards in normalized coordinates), thus consuming move #1.
    if first == 'C':
        cx += 1
        ans += 1

    # If capture already happened
    if cx == tx and cy == ty:
        sys.stdout.write(str(ans) + "\n")
        return

    # --- 1D case: width m == 1 (a single column path) ---
    if m == 1:
        # Base chase time (each step effectively costs 2 moves: thief moves in between)
        ans += (n - cx - 1) * 2
        # Parity adjustment because staying put is forbidden
        ans += ((cx ^ tx) & 1)
        sys.stdout.write(str(ans) + "\n")
        return

    # --- 2D case: if opposite chessboard colors, thief can evade forever ---
    # Parity of (x+y) mod2 equals parity of (x xor y) & 1
    if (((cx ^ cy) ^ (tx ^ ty)) & 1) == 1:
        sys.stdout.write("0\n")
        return

    # --- Same color: cop can force capture. Use closed-form formulas. ---
    if abs(cx - tx) == abs(cy - ty):
        # Normalize so cop is not left of thief: ensure cy >= ty by reflecting horizontally
        if cy < ty:
            cy = (m + 1) - cy
            ty = (m + 1) - ty

        # Diagonal-case formula, multiplied by 2 for alternating turns
        ans += (cy - cx + n - 2) * 2
        sys.stdout.write(str(ans) + "\n")
        return

    # General case formula
    ans += (n - cx - 1 + max(cy - 1, m - cy)) * 2
    sys.stdout.write(str(ans) + "\n")


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

---

## 5) Compressed editorial

- Normalize by symmetry: swap axes if \(|dx|<|dy|\) so \(|dx|\ge|dy|\); reflect vertically so \(x_c\le x_t\).
- If cop moves first, perform one cop step in \(+x\) direction and set `ans=1`.
- If grid is 1D (`m==1` after normalization): capture is forced; answer is
  \((n-x_c-1)\cdot 2 + ((x_c \oplus x_t)\&1)\) plus any initial `ans`.
- If both dimensions > 1 and initial chessboard colors differ: thief can avoid forever ⇒ output `0`.
- Otherwise capture is forced:
  - If \(|dx|=|dy|\) (diagonal case), possibly reflect horizontally so \(y_c\ge y_t\), then
    `ans += (y_c - x_c + n - 2) * 2`.
  - Else
    `ans += (n - x_c - 1 + max(y_c-1, m-y_c)) * 2`.
- Output `ans`.
