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

335. Thiefs And Cops
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



A cop is pursuing a thief in a rectangular HxW grid. Both thief and cop occupy one cell of the grid. Initially they are placed in it somehow, and then make moves in turn. At each move one must go from a cell to any of the cells adjacent to it side-by-side. Note that it's not allowed to stay in the same cell. It's also not allowed to move outside the grid.

The cop catches the thief if they're in the same cell. The aim of the cop is to catch the thief as fast as possible, the aim of the thief is not to be caught, or at least to be free for as many moves as possible. They both see each other and the walls of the grid, so they always know the coordinates of themselves and of each other.

If both players play optimally, will the cop catch the thief, and if he will, after which move it will happen? (moves are numbered starting from 1, for example, if the cop moves first, then move 1 is the cop's move, move 2 is the thief's move, move 3 is the cop's move, etc)

Input
The first line of input contains two integers H and W, 1 ≤ H, W ≤ 5·108, denoting the number of rows and columns in the grid, respectively. The rows are numbered 1 through H, the columns are numbered 1 through W.

The second line of input contains two integers Rc and Cc, 1 ≤ Rc ≤ H, 1 ≤ Cc ≤ W, denoting the row and column of the cell where the cop resides initially.

The third line of input contains two integers Rt and Ct, 1 ≤ Rt ≤ H, 1 ≤ Ct ≤ W, denoting the row and column of the cell where the thief resides initially.

Initial positions of the cop and the thief differ.

The fourth line of input contains either the letter 'C' (capital English letter C) — if the cop moves first, or the letter 'T' (capital English letter T) — if the thief moves first (without quotes).

Output
If the cop can catch the thief with both of them playing optimally, output the number of the move after which it will happen. Otherwise, output 0 (zero).

Example(s)
sample input
sample output
2 2
1 2
2 1
C
0

sample input
sample output
2 2
1 2
2 1
T
2

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

Given 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 still is forbidden.

The cop wants to catch the thief as soon as possible; the thief wants to avoid capture (or delay it). Both play optimally and know both positions.

Output the global move number when they first occupy the same cell; if the thief can avoid capture forever, output `0`.

Constraints: \(1 \le H, W \le 5\cdot 10^8\), so the solution must be \(O(1)\).

---

## 2) Key observations needed to solve the problem

### A) Symmetry reductions (normalize the geometry)
The grid is symmetric under:
- swapping axes (rows \(\leftrightarrow\) columns),
- reflecting vertically \(x \mapsto H+1-x\),
- reflecting horizontally \(y \mapsto W+1-y\).

These transformations preserve whether capture is possible and the capture time (just in transformed coordinates). We use them to reduce to a small set of cases.

### B) Bipartite (chessboard) parity in 2D
For \(H>1\) and \(W>1\), the grid graph is bipartite by color \((r+c)\bmod 2\).
Every move flips color.

A known result used by the reference solution:
- If both dimensions \(>1\) and cop & thief start on **different colors**, the thief can evade forever ⇒ answer `0`.
- If they start on the **same color**, the cop can force capture, and the time can be computed by closed-form formulas after normalization.

### C) 1D case behaves differently
If \(H=1\) or \(W=1\), the graph is a path (a line). With forced movement (no "pass"), the cop will eventually catch the thief; the exact move count depends on parity and distance to the end.

### D) Handling who moves first
We can incorporate "cop moves first" by applying the cop's first optimal move immediately in the normalized coordinate system, increasing the answer by 1, and then solving the remaining game as if the thief is to move next.

---

## 3) Full solution approach

Let cop be \((x_c, y_c)\), thief be \((x_t, y_t)\), and grid be \(n \times m\) (we will rename after normalization).

### Step 1: Normalize so vertical separation dominates
If \(|x_c-x_t| < |y_c-y_t|\), swap axes for both players and swap \(n \leftrightarrow m\).
After that, we have \(|x_c-x_t| \ge |y_c-y_t|\).

### Step 2: Normalize so cop is not below thief
If \(x_c > x_t\), reflect vertically:
\[
x \leftarrow (n+1)-x
\]
Now \(x_c \le x_t\).

### Step 3: If cop moves first, "spend" that move
If first mover is `C`, apply:
- \(x_c \leftarrow x_c + 1\)
- `ans += 1`

If now cop == thief, output `ans` (capture happened on that move).

*(Under our normalization, moving \(+1\) in \(x\) is the natural "close the dominant gap" move used in the known optimal derivation.)*

### Step 4: Solve based on dimension/parity/case formulas

#### Case A: 1D grid (after swap, this appears as `m == 1`)
Then capture is guaranteed; the closed form used is:
- `ans += (n - x_c - 1) * 2`
- `ans += ((x_c ^ x_t) & 1)`  (parity tweak)

Output `ans`.

#### Case B: 2D grid and different chessboard colors ⇒ infinite evasion
If \((x_c+y_c)\bmod 2 \ne (x_t+y_t)\bmod 2\), output `0`.

In code we can test parity via LSB of xor:
\[
(x+y)\bmod 2 = (x \oplus y)\&1
\]
So "different colors" is:
```text
(((x_c ^ y_c) ^ (x_t ^ y_t)) & 1) == 1
```

#### Case C: 2D grid, same color ⇒ capture time formulas
Now capture is forced. Two subcases:

1) **Diagonal case:** \(|x_c-x_t| = |y_c-y_t|\)
   If \(y_c < y_t\), reflect horizontally so \(y_c \ge y_t\).
   Then:
   ```text
   ans += (y_c - x_c + n - 2) * 2
   ```

2) **General case (not diagonal):**
   ```text
   ans += (n - x_c - 1 + max(y_c - 1, m - y_c)) * 2
   ```

Finally print `ans`.

All operations are constant time and fit easily in 64-bit signed integers.

---

## 4) C++ implementation

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

---

## 5) Python implementation with detailed comments

```python
import sys

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

    n = int(next(it))   # height
    m = int(next(it))   # width

    xc = int(next(it)); yc = int(next(it))
    xt = int(next(it)); yt = int(next(it))

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

    # --- Step 1: Ensure |dx| >= |dy| by swapping axes if needed ---
    if abs(xc - xt) < abs(yc - yt):
        xc, yc = yc, xc
        xt, yt = yt, xt
        n, m = m, n

    # --- Step 2: Ensure cop is not below thief (xc <= xt) via vertical reflection ---
    if xc > xt:
        xc = (n + 1) - xc
        xt = (n + 1) - xt

    ans = 0

    # --- Step 3: If cop moves first, apply cop's first move (+x) immediately ---
    if first == 'C':
        xc += 1
        ans += 1

    # Capture immediately?
    if xc == xt and yc == yt:
        sys.stdout.write(str(ans) + "\n")
        return

    # --- Step 4A: 1D case ---
    if m == 1:
        ans += (n - xc - 1) * 2
        ans += ((xc ^ xt) & 1)
        sys.stdout.write(str(ans) + "\n")
        return

    # --- Step 4B: 2D parity check: different colors => infinite evasion ---
    if (((xc ^ yc) ^ (xt ^ yt)) & 1) == 1:
        sys.stdout.write("0\n")
        return

    # --- Step 4C: same color => capture guaranteed, use closed forms ---

    # Diagonal case
    if abs(xc - xt) == abs(yc - yt):
        # Reflect horizontally so yc >= yt
        if yc < yt:
            yc = (m + 1) - yc
            yt = (m + 1) - yt

        ans += (yc - xc + n - 2) * 2
        sys.stdout.write(str(ans) + "\n")
        return

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


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

These implementations follow the same constant-time case analysis as the provided reference solution, making them suitable for very large grids.
