Scheduling Two Meetings

Time limit1sMemory limit2048 MB

Summary

Given n time slots with a Y/N on-site mask over m judges, pick two slots whose on-site sets cover every judge and share the most on-site judges.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming
Solved: No attempts yet

문제

You are the chief judge of the International Collegiate Quiz Contest (ICQC) this year. You want to hold judge meetings twice to prepare the problem set for the contest. You proposed several candidate schedules for the meetings, and every judge answered, for each time slot, whether they would attend on-site or remotely through a video conference tool.

Choose two distinct time slots so that every judge attends at least one of the two meetings on-site. If several pairs qualify, choose the pair with the largest number of judges attending both meetings on-site. If pairs still tie, choose the one with the earlier first meeting. If the first meetings also tie, choose the one with the earlier second meeting.

Input

The first line contains two integers $n$ and $m$ . $n$ ( $2 \le n \le 2 \times 10^5$ ) is the number of candidate time slots, numbered 1 through $n$ , where a smaller number is an earlier slot. $m$ ( $2 \le m \le 20$ ) is the number of judges.

Each of the next $n$ lines contains $m$ characters. $a_{i,j}$ is Y if judge $j$ attends the meeting at slot $i$ on-site, and N if judge $j$ attends remotely.

Output

Print the two time slot numbers of the best pair on one line, separated by a space, with the earlier slot first. If no pair satisfies the condition, print No.

Examples5

Example 1
Input
```
4 3
NNY
YYN
YNY
NYY
```
Expected output
```
2 3
```
Example 2
Input
```
3 6
NNNYYY
YYNYYN
YYYNNN
```
Expected output
```
1 3
```

Example 3

Input

6 5
NNNNN
YNNNY
YYNNN
YYNNN
NYYNY
NNYYY

Expected output

3 6

Example 4
Input
```
3 3
YNN
NYN
NNY
```
Expected output
```
No
```
Example 5
Input
```
4 4
NYNN
YNYY
YNYN
NNYY
```
Expected output
```
1 2
```