## DMOPC '21 Contest 9 P4 - Ace of Diamonds

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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:

1. A coin may only be removed from the grid if it is heads.
2. 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!

#### Constraints

and are both odd positive integers.

#### Input Specification

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.

#### Output Specification

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

-1