Thief
A cop is pursuing a thief in a rectangular h * w 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 contains two integers h and w (1 ≤ h, w ≤ 5 * 10^8), 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 contains two integers R[c] and C[c] (1 ≤ R[c] ≤ h, 1 ≤ C[c] ≤ w), denoting the row and column of the cell where the cop resides initially.
The third line contains two integers R[t] and C[t] (1 ≤ R[t] ≤ h, 1 ≤ C[t] ≤ 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 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.
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).