Amidst his journey through the Borderlands, Arisu stumbles upon a diamonds game involving an 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!
and are both odd positive integers.
Subtask 1 [25%]
Subtask 2 [75%]
No additional constraints.
The first line contains integers and .
The next lines each contain a string of characters. The -th character of the -th string is
H if the coin in cell is initially heads, or
T if it is initially tails.
If it is impossible to beat the game, output on its own line.
Otherwise, output lines. The -th of these should contain space-separated integers and , indicating that the coin in cell should be the -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