AT_icpc2015summer_day4_a Where is the Boundary

### 问题描述 在某个星球上，有一个狭长的岛国 JAGAN，它东西延伸。这个狭长的国家被认为由两个主要的文化区域组成——东部和西部。东部地区倾向于具有东部文化特征，而西部地区倾向于具有西部文化特征。当然，这两个文化区域之间的边界并不清晰，这已经成为一个问题。 你被分配了一个任务，使用给定的数据集来估计这个边界。 任务的更精确规范如下： 1. JAGAN 被划分为 $n$ 个县，这些县在东西方向上形成一条直线。每个县从西到东编号为 $1, 2, \ldots, n$。 2. 每个数据集由 $m$ 个特征组成，每个特征对每个县都有 `E`（东部）或 `W`（西部）的标记。这些数据表明每个县从 $m$ 个不同的角度（例如食物、服装等）具有东部或西部的特征。 3. 在估计中，你需要选择一个文化边界，使得错误最小化。也就是说，你需要最小化东部一侧的 `W` 和西部一侧的 `E` 的总和。 4. 在估计中，你只能选择两个县之间的边界作为文化边界。 有时，所有县可能都被估计为东部或西部文化区域。在这些情况下，为了简化，你必须虚拟地考虑边界位于第 $0$ 县和第 $1$ 县之间，或者第 $n$ 县和第 $n+1$ 县之间。 当你有多个最小值时，你必须输出最西边的（编号最小的）结果。 编写一个程序来解决这个任务。

每个输入的格式如下： $n$ $m$ $d_{11}$ $\ldots$ $d_{1n}$ $\ldots$ $d_{m1}$ $\ldots$ $d_{mn}$ 第一行包含两个整数 $n$（$1 \le n \le 10{,}000$）和 $m$（$1 \le m \le 100$），表示县的数目和任务中的特征数目。接下来的$m$行是任务中给定的数据集。每行包含恰好 $n$ 个字符。第 $i$ 行的第 $j$ 个字符 $d_{ij}$ 是 `E`（东部）或 `W`（西部），表示第 $j$ 县从第 $i$ 个角度具有东部或西部的特征。

在一行中打印估计的结果。输出由两个按升序排列的整数组成，表示接触边界的两个县。 ### 样例解释 #### 样例输入1 ``` 2 1 WE ``` #### 样例输出1 ``` 1 2 ``` #### 样例输入2 ``` 3 2 WWE WEE ``` #### 样例输出2 ``` 1 2 ``` 两个估计`1 2`和`2 3`都达到了1个错误作为最小值。根据你必须采用最西边的估计的限制，你必须输出`1 2`。 #### 样例输入3 ``` 3 1 WWW ``` #### 样例输出3 ``` 3 4 ``` 在这种情况下，所有县都是西部的。如问题陈述中所述，你必须虚拟地考虑边界位于第三和第四县之间。 #### 样例输入4 ``` 3 1 WEW ``` #### 样例输出4 ``` 1 2 ``` 你不能假设 `E` 和 `W` 是分开的。 --- 翻译：@[zengyukai2012](https://www.luogu.com.cn/user/1090444)