Amidst his journey through the Borderlands, Arisu stumbles upon a diamonds game involving an ~N \times M~ grid of coins. The goal of the game is to remove all of the coins, one by one, under the following two conditions:
- A coin may only be removed from the grid if it is heads.
- When a coin is removed, the coins in the cells that share an edge with it are flipped (if they exist).
Unfortunately, diamonds is not one of Arisu's strong suits. Help him beat the game, or determine that it's impossible to do so!
~1 \le N \times M \le 10^6~
~N~ and ~M~ are both odd positive integers.
Subtask 1 [25%]
~N = 1~
Subtask 2 [75%]
No additional constraints.
The first line contains ~2~ integers ~N~ and ~M~.
The next ~N~ lines each contain a string of ~M~ characters. The ~j~-th character of the ~i~-th string is
H if the coin in cell ~(i, j)~ is initially heads, or
T if it is initially tails.
If it is impossible to beat the game, output ~-1~ on its own line.
Otherwise, output ~N \times M~ lines. The ~i~-th of these should contain ~2~ space-separated integers ~r_i~ ~(1 \le r_i \le N)~ and ~c_i~ ~(1 \le c_i \le M)~, indicating that the coin in cell ~(r_i, c_i)~ should be the ~i~-th coin removed. If there are multiple valid solutions, output any of them.
Sample Input 1
3 3 HTH THT HTH
Sample Output 1
2 2 1 1 1 3 3 1 3 3 1 2 2 1 2 3 3 2
Sample Input 2
1 3 HHT
Sample Output 2