<|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’ll 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:
```cpp
(((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 with detailed comments

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

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

    long long n, m;                 // grid after normalization (height=n, width=m)
    long long xc, yc, xt, yt;       // cop (xc,yc), thief (xt,yt)
    char first;                     // 'C' or 'T'

    cin >> n >> m;
    cin >> xc >> yc;
    cin >> xt >> yt;
    cin >> first;

    // --- Step 1: Ensure |dx| >= |dy| by possibly swapping axes ---
    if (llabs(xc - xt) < llabs(yc - yt)) {
        swap(xc, yc);
        swap(xt, yt);
        swap(n, m);
    }

    // --- Step 2: Ensure cop is not below thief: xc <= xt by vertical reflection ---
    if (xc > xt) {
        xc = (n + 1) - xc;
        xt = (n + 1) - xt;
        // y unchanged by vertical reflection
    }

    long long ans = 0;

    // --- Step 3: If cop moves first, apply the cop's first move in +x direction ---
    if (first == 'C') {
        xc += 1;   // one step down in normalized coordinates
        ans += 1;  // capture would be after move #1 if it happens now
    }

    // If capture already happened after that move
    if (xc == xt && yc == yt) {
        cout << ans << "\n";
        return 0;
    }

    // --- Step 4A: 1D case (single column) ---
    // (After our potential swap, "m==1" represents a path of length n.)
    if (m == 1) {
        // Each "layer" effectively consumes 2 moves (thief moves between cop moves).
        ans += (n - xc - 1) * 2;

        // Parity correction because neither player may stay in place.
        ans += ((xc ^ xt) & 1);

        cout << ans << "\n";
        return 0;
    }

    // --- Step 4B: 2D case; check bipartite parity ---
    // Different chessboard colors => thief can evade forever.
    if ( (((xc ^ yc) ^ (xt ^ yt)) & 1LL) ) {
        cout << 0 << "\n";
        return 0;
    }

    // --- Step 4C: Same color => capture is guaranteed, use formulas ---

    // Diagonal subcase: |dx| == |dy|
    if (llabs(xc - xt) == llabs(yc - yt)) {
        // Normalize horizontally so yc >= yt by reflecting y if needed.
        if (yc < yt) {
            yc = (m + 1) - yc;
            yt = (m + 1) - yt;
        }

        ans += (yc - xc + n - 2) * 2;
        cout << ans << "\n";
        return 0;
    }

    // General subcase
    ans += ( (n - xc - 1) + max(yc - 1, m - yc) ) * 2;
    cout << ans << "\n";
    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.