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 ≤ RcH, 1 ≤ CcW, 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 ≤ RtH, 1 ≤ CtW, 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




Online Contester Team © 2002 - 2010. All rights reserved.