Sample Input 1

3 7
E
E
E
L 2
E
L 1
E

Sample Output 1

1 1
3 2
1 2
3 1
1 1

Sample Input 2

10 9
E
E
E
E
L 3
E
E
L 6
E

Sample Output 2

1 1
10 2
5 2
7 1
4 2
2 2
4 1

Subtask

• 25% số điểm có ~N \le 150, M \le 150~;
• 20% số điểm có ~N \le 1500, M \le 1500~;
• 20% số điểm có ~N \le 150 000, M \le 1500~;
• 35% số điểm không có ràng buộc gì thêm.