Where is the Boundary

Interview

Time limit5sMemory limit512 MB

Summary

Given m binary strings of length n, cut the line between two prefectures and label each side east or west to minimize mismatches. Report the two prefectures meeting at the best cut, choosing the westernmost one on ties.

Level: Medium5 of 10
Topics: Prefix sum, Array, Greedy, Implementation
Solved: No attempts yet

Problem

An island country named JAGAN on 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 eastern cultural features and regions in the west tend to have western cultural features, but the boundary between the two cultural areas is not clear, which has been an issue.

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

The assignment is specified as follows:

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.
Each data set consists of $m$ features, each of which is 'E' (east) or 'W' (west) for every prefecture. These data indicate whether each prefecture has eastern or western features from $m$ different points of view, for example food, clothing, and so on.
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.
In the estimation, you can choose a cultural boundary only from the boundaries between two prefectures.

Sometimes all prefectures may be estimated to be in 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.

Input

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$ ) and $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 whether the $j$ -th prefecture has the eastern or the western feature from the $i$ -th point of view.

Output

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

Examples4

Example 1
Input
```
2 1
WE
```
Expected output
```
1 2
```
Example 2
Input
```
3 2
WWE
WEE
```
Expected output
```
1 2
```
Example 3
Input
```
3 1
WWW
```
Expected output
```
3 4
```
Example 4
Input
```
3 1
WEW
```
Expected output
```
1 2
```