시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 3 3 3 100.000%

문제

An island country JAGAN in a certain planet is very long and narrow, and extends east and west. This long country is said to consist of two major cultural areas — the eastern and the western. Regions in the east tend to have the eastern cultural features and regions in the west tend to have the western cultural features, but, of course, the boundary between the two cultural areas is not clear, which has been an issue.

You are given an assignment estimating the boundary using a given data set.

More precise specification of the assignment is as follows:

1. JAGAN is divided into $n$ prefectures forming a line in the east-west direction. Each prefecture is numbered 1, 2, ..., $n$ from WEST to EAST.
2. Each data set consists of $m$ features, which has 'E' (east) or 'W' (west) for each prefecture. These data indicate that each prefecture has eastern or western features from $m$ different point of views, for example, food, clothing, and so on.
3. In the estimation, you have to choose a cultural boundary achieving the minimal errors. That is, you have to minimize the sum of 'W's in the eastern side and 'E's in the western side.
4. In the estimation, you can choose a cultural boundary only from the boundaries between two prefectures.

Sometimes all prefectures may be estimated to be the eastern or the western cultural area. In these cases, to simplify, you must virtually consider that the boundary is placed between prefecture No. 0 and No. 1 or between prefecture No. $n$ and No. $n+1$. When you get multiple minimums, you must output the most western (least-numbered) result.

Write a program to solve the assignment.

입력

Each input is formatted as follows:

$n$ $m$
$d_{11}$...$d_{1n}$
...
$d_{m1}$...$d_{mn}$

The first line consists of two integers $n$ ($1 \le n \le 10{,}000$), $m$ ($1 \le m \le 100$), which indicate the number of prefectures and the number of features in the assignment. The following $m$ lines are the given data set in the assignment. Each line contains exactly $n$ characters. The $j$-th character in the $i$-th line $d_{ij}$ is 'E' (east) or 'W' (west), which indicates $j$-th prefecture has the eastern or the western feature from the $i$-th point of view.

출력

Print the estimated result in a line. The output consists of two integers sorted in the ascending order which indicate two prefectures touching the boundary.

예제 입력 1

2 1
WE


예제 출력 1

1 2


예제 입력 2

3 2
WWE
WEE


예제 출력 2

1 2


Both estimates "1 2" and "2 3" achieve 1 error as the minimum. From the restriction that you must adopt the most western estimate, you must output "1 2".

예제 입력 3

3 1
WWW


예제 출력 3

3 4


In this case, all the prefectures are western. As described in the problem statement, you must virtually consider that the boundary is placed between third and fourth prefectures.

예제 입력 4

3 1
WEW


예제 출력 4

1 2


You cannot assume that 'E's and 'W's are separated.