题目描述

在一个 $H\times W$ 的方格棋盘上，一名警察正在追捕一名小偷。两人分别占据一个格子，初始位置不同，之后轮流移动。

每次移动必须走到一个上下左右相邻的格子，不能原地不动，也不能走出棋盘。如果某次移动后警察和小偷位于同一格，则小偷被抓住。

警察希望尽快抓住小偷；小偷希望永远不被抓住，如果无法逃脱，则希望尽可能晚被抓住。双方均知道彼此位置和棋盘边界，并采用最优策略。

求警察是否一定能抓住小偷；若能，输出发生抓捕的是全局第几次移动，否则输出 0。

输入格式

第一行两个整数 $H,W$，$1\le H,W\le5\cdot10^8$。

第二行两个整数 $R_c,C_c$，表示警察初始位置。

第三行两个整数 $R_t,C_t$，表示小偷初始位置。保证两者不同。

第四行一个字符：C 表示警察先手，T 表示小偷先手。

输出格式

若警察在双方最优策略下可以保证抓住小偷，输出抓捕发生的移动编号；否则输出 0。

样例 1

2 2
1 2
2 1
C

0

样例 2

2 2
1 2
2 1
T

2